#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

struct muchie
{
    int nod, cost;
}temp;

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

vector<muchie> mu[100005];
queue<int> q;
bool vis[100005];
int dist[100005];
//int last_visited_node_before_crt[100005];

void dijkstra(int start)
{
    q.push(start);

    while(!q.empty())
    {
        int aux = q.front();
        vis[aux] = 1;
        //out<<aux<<" : ";

        for(int i = 0 ; i < mu[aux].size() ; i++)
        {
            if(!vis[mu[aux][i].nod])
            {
                //out<<mu[aux][i].nod<<" , ";
                q.push(mu[aux][i].nod);
                if( dist[aux] + mu[aux][i].cost < dist[mu[aux][i].nod] || dist[mu[aux][i].nod] == 0)
                {
                    dist[mu[aux][i].nod] = dist[aux] + mu[aux][i].cost;
                    //last_visited_node_before_crt[mu[aux][i].nod] = aux;
                }
            }
        }
        //out<<'\n';

        q.pop();
    }
}

void sortare(int n)
{
    for(int i = 1; i <= n ;i++)
    {
        sort(mu[i].begin(), mu[i].end(), cmp);
    }
}

void afisare(int n)
{
    int i, j;
    for(int j = 1 ; j <= n; j++)
    {
        out<< j <<" : ";
        for(int i = 0 ; i < mu[j].size() ; i++)
        {
            out<<" nodu : " << mu[j][i].nod << " cost : " <<  mu[j][i].cost <<" , ";
        }
        out<<'\n';
    }
}

void citire(int m)
{
    int j, i;
    for(j = 1 ; j <= m; j++)
    {
        int y;
        in >> y >> temp.nod >> temp.cost;
        mu[y].push_back(temp);
    }
}

int main()
{
    int i, n, m;

    in >> n >> m;

    citire(m);

    sortare(n);

//    afisare(n);
//    return 0;

    dijkstra(1);

    for(i = 2 ; i <= n ; i++)
    {
        out<<dist[i]<<" ";
    }
    return 0;
}