#include<stdio.h>
#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];   // vecinii
vector <int> c[MAXN];   // costul

int N, M, lHP;
int Cmin[MAXN], viz[MAXN], HP[3*MAXN], poz[MAXN];

    // Cmin = costul mini (ce trebuie afisat)
    // poz = pozitia in HP = Heap

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

    fscanf(f,"%d %d\n",&N,&M);
    for(i=1;i<=M;i++){

        fscanf(f,"%d %d %d\n",&x,&y,&z);
        v[x].push_back(y);
        c[x].push_back(z);

    }

    for(i=2;i<=N;i++)
        Cmin[i] = INF;

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

}

void inv( int &P1, int P2 ){

    swap( HP[P1], HP[P2] );
    swap( poz[HP[P1]], poz[HP[P2]] );
    P1 = P2;

}

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

    // in sus
    while( p > 1 && Cmin[ HP[p] ] < Cmin[ HP[p/2] ] )
        inv( p, p/2 );

    // in jos
    while(1){

        NEWCmin = INF;
        if( p*2 <= lHP ){
            NEWCmin = Cmin[ HP[p*2] ];
            NEWp = p*2;
        }
        if( p*2+1 <= lHP && Cmin[ HP[p*2+1] ] < NEWCmin ){
            NEWCmin = Cmin[ HP[p*2+1] ];
            NEWp = p*2+1;
        }

        if( Cmin[HP[p]] > NEWCmin )
            inv( p, NEWp );
        else
            break;

    }

}

void Rezolvare(){
int i, j, nod, cost, NEWnod, NEWcost;

    for(i=1;i<=N-1;i++){    // Cu N-1 noduri putem face ceva

        nod  = HP[1];
        cost = Cmin[nod];

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

            NEWnod  = v[nod][j];
            NEWcost = c[nod][j];

            if( cost + NEWcost < Cmin[NEWnod] ){

                Cmin[NEWnod] = cost + NEWcost;
                Echilibreaza( poz[NEWnod] );

            }

        }

        HP[1] = HP[lHP];    // Eliminam elementul din varf
        lHP--;
        Echilibreaza(1);

        viz[nod] = 1;

    }

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

int main(){

    Citire();
    Rezolvare();

return 0;
}