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

using namespace std;

vector < pair<int,int> > v[DIMN];
queue <int> Q;

int N, M, D[DIMN], vizQ[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 ) );

    }

}

void BF( int nodSTART ){
int i, nod, vecin, cost;

    for(i=1;i<=N;i++)
        D[i] = INF;
        D[ nodSTART ] = 0;

    Q.push( nodSTART );
    vizQ[ nodSTART ] = 1;

    while( !Q.empty() ){

        nod = Q.front();

        Q.pop();
        vizQ[ nod ] = 0;

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

            vecin = v[nod][i].first;
            cost = v[nod][i].second;

            if( D[vecin] > D[nod] + cost ){

                D[vecin] = D[nod] + cost;

                if( vizQ[vecin] == 0 ){

                    vizQ[vecin] = 1;
                    Q.push(vecin);

                }

            }

        }

    }

}

void Afisare(){
int i;

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

}

int main(){

    Citire();
    BF(1);
    Afisare();

return 0;
}