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

using namespace std;

vector < pair<int,int> > v[DIM];

int N, M, d[DIM], HP[2*DIM], lHP, poz[DIM];  // Cum e daca pun 2*DIM

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) );

    }

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

    lHP = N;

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

}

void Intersch( int &p1, int p2 ){

    swap( HP[p1], HP[p2] );
    swap( poz[ HP[p1] ], poz[ HP[p2] ] );

    p1 = p2;

}

void Calibreaza( int p ){
int i, pmin, dmin;

    // Urca
    while( p > 1 && d[ HP[p/2] ] > d[ HP[p] ] ){
        Intersch(p,p/2);
    }

    // Coboara
    while(1){

        pmin = p;
        dmin = d[ HP[pmin] ];

        if( p*2 <= lHP && d[ HP[p*2] ] < dmin ){
            dmin = d[ HP[ p*2 ] ];
            pmin = p*2;
        }

        if( p*2+1 <= lHP && d[ HP[p*2+1] ] < dmin ){
            dmin = d[ HP[ p*2+1 ] ];
            pmin = p*2+1;
        }

        if( pmin != p )
            Intersch(p,pmin);
        else
            break;

    }

}

void Rezolvare(){
int i, j, nod, cos, NEWnod, NEWcos, vf;

    for(j=1;j<=N;j++){

        nod = HP[1];
        cos = d[nod];

        vf = 1;
        Intersch(vf,lHP);  // Elimina nodul
        lHP --;
        Calibreaza(1);

        if( cos != INF ){
            for(i=0;i<v[nod].size();i++){

                NEWnod = v[nod][i].first;
                NEWcos = v[nod][i].second;

                if( d[NEWnod] > cos + NEWcos ){

                    d[NEWnod] = cos + NEWcos;

                    Calibreaza( poz[NEWnod] );

                }

            }
        }

    }

    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;
}