#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int n, m, viz[100002], k;
long long d[100002];
struct node{
    int inf, dist;
    struct node *next;
}*l[100004],*p;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

priority_queue <pair<int, int>, vector<pair<int,int> >, greater<pair<int,int> > >pq;

void citire(){
    in >> n >> m;
    k = 1;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        in >> x >> y >> c;

        p = new node;
        p -> inf = y;
        p -> dist = c;
        p -> next = l[x];
        l[x] = p;

        /*p = new node;
        p -> inf = x;
        p -> dist = c;
        p -> next = l[y];
        l[y] = p;*/
    }
}

void dijkstra(){
    const long long INF = 1e18;
    for(int i = 1; i <= n; i++) d[i] = INF;

    d[k] = 0;
    p = l[k];

    while(p != NULL){
        d[p -> inf] = p -> dist;
        pq.push(make_pair(d[p -> inf],p -> inf));
        p = p -> next;
    }

    viz[k] = 1;
    pq.push(make_pair(d[k],k));

    while(!pq.empty()){
        int nmin;
        nmin = pq.top().second;
        pq.pop();

        p = l[nmin];
        while(p != NULL){
            if(d[p -> inf] > d[nmin] + p -> dist){
                d[p -> inf] = d[nmin] + p -> dist;
                pq.push(make_pair(d[p -> inf], p -> inf));
            }
            p = p -> next;
        }
    }

    for(int i = 2; i <= n; i++)
    if(d[i] == INF) out << "0 ";
    else out << d[i] << " ";
}

int main()
{
    for(int i = 1; i <= n; i++) l[i] = NULL;
    citire();
    /*for(int i = 1; i <= n; i++){
        p = l[i];
        cout << i << " : ";
        while(p != NULL){
            cout << p -> inf << "(" << p -> dist << "), ";
            p = p -> next;
        }
        cout << "\n";
    }*/
    dijkstra();
    return 0;
}