#include<stdio.h>
#include<algorithm>
#include<vector>
#define MAXN 50005
#define MAXM 250005
#define INF 2000000000
FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");

using namespace std;

vector <int> v[MAXN]; // vecinul
vector <int> c[MAXN]; // costul

long int N, M, hHP, R[MAXN], HP[MAXN], Poz[MAXN], viz[MAXN];

    // HP = heap-ul, care contine nodurile
    // Poz[i] = Nodul i pe ce pozitie e in HP

void Citire(){
long int i, X, Y, C;

    fscanf(f,"%ld %ld\n",&N,&M);
    for(i=1;i<=M;i++){
        fscanf(f,"%ld %ld %ld\n",&X,&Y,&C);
        v[X].push_back(Y); c[X].push_back(C);
    }
    for(i=2;i<=N;i++) R[i] = INF;

}

void inv( long int A, long int B ){
    swap( HP[A], HP[B] );
    swap( Poz[A], Poz[B] );
}

void Calibreaza( long int p ){
long int i, minim, fiu;

    // urca
    while( p > 1 && R[ HP[p/2] ] > R[ HP[p] ] ){ inv(p,p/2); p/=2; }

    // coboara
    while( p * 2 <= hHP ){

        minim = R[ HP[p*2] ]; fiu = p*2;
        if( p*2 +1 <= hHP && R[ HP[p*2+1] ] < minim ){ minim = R[ HP[p*2+1] ]; fiu = p*2+1; }

        if( R[ HP[p] ] > minim ){ inv(p,fiu); p = fiu; }
        else break;
    }

}

void Rezolvare(){
long int i, j, nod, nod2, cost2;

    for(i=1;i<=N;i++){ R[i]=INF; HP[i]=i; Poz[i]=i; } R[1]=0; hHP=N;

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

        nod = HP[1]; viz[nod]=1;
        inv( 1, hHP ); hHP--;
        Calibreaza(1);

        for(j=0;j<v[nod].size();j++){
            nod2 = v[nod][j]; cost2 = c[nod][j];
            if( viz[nod2] == 0 ){
                R[nod2] = min( R[nod] + cost2 , R[nod2] );
                Calibreaza( Poz[nod2] );
            }
        }

    }
    for(i=2;i<=N;i++) fprintf(g,"%ld ",R[i]);

}

int main(){

    Citire();
    Rezolvare();

return 0;
}