#include<cstdio>
#include<vector>
#include<algorithm>
#define MAXN 50005
#define INF 1000000000
FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");

using namespace std;

vector <int> v[MAXN], c[MAXN];

int N, M, d[MAXN], HP[3*MAXN], LHP, poz[MAXN];
bool viz[MAXN];

void Citire(){
int i, x, y, cst;

    fscanf(f,"%d %d\n",&N,&M);

    for(i=1;i<=M;i++){

        fscanf(f,"%d %d %d\n",&x,&y,&cst);

        v[x].push_back(y);
        c[x].push_back(cst);

    }

}

void Echilibreaza( int p ){
int NEWp, NEWd;

    // Urca

    while( p > 1 && d[ HP[p/2] ] > d[ HP[p] ] ){

        swap( poz[HP[p]], poz[HP[p/2]] );
        swap( HP[p], HP[p/2] );

        p /= 2;

    }

    // Coboara

    while( p*2 <= LHP ){

        NEWp = p;
        NEWd = d[ HP[p] ];

        if( p*2 <= LHP && d[ HP[p*2] ] < NEWd ){

            NEWp = p*2;
            NEWd = d[ HP[p*2] ];

        }

        if( p*2+1 <= LHP && d[ HP[p*2+1] ] < NEWd ){

            NEWp = p*2+1;
            NEWd = d[ HP[p*2+1] ];

        }

        if( p == NEWp )
            break;

        else{

            swap( HP[p], HP[NEWp] );
            swap( poz[HP[p]], poz[HP[NEWp]] );

            p = NEWp;

        }

    }

}

void Rezolvare(){
int i, j, NOD, NODnou, COSTnou;

    for(i=1;i<=N;i++)
        d[i] = INF;
        d[1] = 0;

    for(i=1;i<=N;i++){
        poz[i] = i;
        HP[i] = i;
    }   LHP = N;

    for(i=1;i<=N-1;i++){

        NOD = HP[1];
        viz[NOD] = 1;

        for(j=0;j<v[NOD].size();j++){

            NODnou = v[NOD][j];

            COSTnou = d[NOD] + c[NOD][j];

            if( COSTnou < d[NODnou] ){

                d[NODnou] = COSTnou;

                Echilibreaza( poz[NODnou] );

            }

        }

        HP[1] = HP[LHP];
        poz[ HP[1] ] = 1;
        LHP --;
        Echilibreaza(1);

    }

    for(i=2;i<=N;i++)
        if( d[i] != INF )
            fprintf(g,"%d ",d[i]);
        else
            fprintf(g,"0 ");

}

int main(){

    Citire();
    Rezolvare();

return 0;
}