#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define inf 2000000000
vector < pair<int,int> > A[50001];
vector < pair<int,int> > :: iterator it;
int N, D[50001], H[50001], P[50001], NH;

void percolate(int x){
    int p,c;
    c = x;
    p = c / 2;
    while( p > 0 && H[p] > H[c] ){
        swap(H[p], H[c]);
        swap(P[p],P[c]);
        c = p;
        p = c / 2;
    }
}

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

}

int main()
{
    int m, i, x, y, c, k, ok, min;
    f >> N >> m;
    for(i = 1; i <= m; i++){
        f >> x >> y >> c;
        A[x].push_back(make_pair(y,c));
    }
    for( i = 1; i <= N; i++ ){
        D[i] = inf;
    }
    D[1] = 0;
    ok = 1;
    NH++;
    H[NH] = 0;
    P[1] = 1;
    while(NH > 0){
        k = P[1];
        del();
        for( it = A[k].begin(); it < A[k].end(); it++ )
            if( D[it->first] > D[k] + it->second ){
                D[it->first] = D[k] + it->second;
                if(P[it->first] == 0){ // nu e in heap
                    NH++;
                    H[NH] = D[k] + it->second;
                    P[NH] = it->first;
                    percolate(NH);
                }
                else
                    percolate(P[it->first]);
            }
    }
    for(i = 2; i <= N; i++)
        if(D[i] == inf)
            g << "0 ";
        else
            g << D[i] << " ";
    return 0;
}