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

using namespace std;

long int N, M, HP[MAXN], LHP, Lmin[MAXN], Poz[MAXN];
bool viz[MAXN];

    // Poz[i] = Nodul i pe ce pozitie e
    // Lmin[i] = Ce lungime minima are nodul i

vector <int> v[MAXN];   // v[i][j] = nodul vecin a lui i
vector <int> c[MAXN];   // c[i][j] = costul de la nodul i la nodul v[i][j]

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

    fscanf(f,"%ld %ld\n",&N,&M);
    for(i=1;i<=M;i++){
        fscanf(f,"%ld %ld %ld\n",&x,&y,&z);
        v[x].push_back(y);
        c[x].push_back(z);
    }
    for(i=1;i<=N;i++) Lmin[MAXN] = INF;

}

void inv(long int A, long int B){

    swap(HP[A],HP[B]);
    swap( Poz[HP[A]], Poz[HP[B]] );

}

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

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

    // Coboara
    while( p*2 <= LHP ){

        fiu = p*2; minim = Lmin[ HP[fiu] ];

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

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

    }

}

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

    for(i=1;i<=N;i++){  // Creare Heap initial
        HP[i]=i;
        Lmin[i]=INF;
        Poz[i]=i;
    }   Lmin[1]=0;
        LHP = N;

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

        nod = HP[1]; viz[nod]=1;
        inv(1,LHP); LHP--; Calibreaza(1); // Scoate minimul

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

    }

}

void Afiseaza(){
long int i;

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

}

int main(){

    Citire();
    Rezolva();
    Afiseaza();

return 0;
}