#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> A[50001];
vector <int> C[50001];
#define inf 1e9
int D[50001], P[50001], H[50001];
int n, m, nh;

void percolate(int x){
    int c, p;
    c=x;
    while (1)
    {
        p=c/2;
        if (p==0)
            break;
        if (D[H[c]]<D[H[p]])
        {
            P[H[c]] = p;
            P[H[p]] = c;
            swap(H[c],H[p]);
            c=p;
        }
        else
            break;
    }
}

void sift(){
    int c, d;
    c=1;
    while (1)
    {
        d=2*c;
        if (d>nh)
            break;
        if (d+1<=nh && D[H[d+1]]<D[H[d]])
            d++;
        if (D[H[c]]>D[H[d]])
        {
            P[H[c]] = d;
            P[H[d]] = c;
            swap(H[c],H[d]);
            c=d;
        }
        else
            break;
    }
}

void citire(){
    int i, x, y, c;
    f >> n >> m;
    for( i = 1; i <= m; i++ ){
        f >> x >> y >> c;
        A[x].push_back(y);
        C[x].push_back(c);
    }
    nh = n;
    for( i = 1; i <= n; i++ ){
        H[i] = P[i] = i;
        D[i] = inf;
    }
    D[1] = 0;
}

void dijkstra(){
    int ok, minim, k, i, x;
    ok = 1;
    while( ok == 1 ){
        minim = D[H[1]];
        k = H[1];
        P[H[1]] = nh;
        P[H[nh]] = 1;
        swap(H[nh], H[1]);
        nh--;
        sift();
        if( minim != inf && nh > 0 ){
            for( i = 0; i < A[k].size(); i++ )

                    if( C[k][i] + D[k] < D[A[k][i]] ){
                        D[A[k][i]] = C[k][i] + D[k];
                        x = P[A[k][i]];
                        percolate(x);
                    }
        }
        else
            ok = 0;
    }
}

int main(){
    citire();
    dijkstra();
    int i;
    for( i = 2; i <= n; i++ )
        if( D[i] == inf )
            g << 0 << " ";
        else
            g << D[i] << " ";
    return 0;
}