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

using namespace std;

int N, M, LHP, HP[DIMN], d[DIMN], poz[DIMN], prec[DIMN];            // HP = heap-ul, d = distantele, viz = vizitat sau nu
                                                                    // poz = pozitia in HP, prec = pentru drumul minim
vector < pair<int,int> > v[DIMN];

void Citire(){

    int i, x, y, c;

    fscanf(f,"%d %d\n",&N,&M);
    for(i=1;i<=M;i++){
        fscanf(f,"%d %d %d\n",&x,&y,&c);
        v[x].push_back( make_pair(y,c) );
        //v[y].push_back( make_pair(x,c) );
    }

}

void Invers( int poz1, int poz2 ){

    swap( HP[poz1], HP[poz2] );
    swap( poz[ HP[poz1] ], poz[ HP[poz2] ] );

}

void Urca( int p ){

    while( p > 1 ){

        if( d[ HP[p] ] < d[ HP[p/2] ] ){
            Invers( p, p/2 );
            p = p/2;
        }
        else break;
    }

}

void Coboara( int p ){

    int pNOU;

    while(1){

        pNOU = p;

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

        if( pNOU != p ){
            Invers( p, pNOU );
            p = pNOU;
        }
        else break;

    }

}

int Pop(){

    int NOD = HP[1];
    Invers( 1, LHP-- );
    Coboara(1);

    return NOD;

}

void Initializari(){

    int i;

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

    d[1] = 0;

}

void Rezolvare(){

    int i, NOD, vNOD, cNOD;
    Initializari();

    LHP = N;
    while( LHP >= 2 ){

        NOD = Pop();                        // Elimin NODul cu cel mai d[] din HP

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

            vNOD = v[NOD][i].first;
            cNOD = v[NOD][i].second;

            if( d[vNOD] > d[NOD] + cNOD ){    // Nu-mi mai tre conditie de viz, ca oricum nu poate da adev
                d[vNOD] = d[NOD] + cNOD;
                Urca( poz[vNOD] );       // Reglare HP
            }

        }

    }

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

}

int main(){

    Citire();
    Rezolvare();

return 0;
}