#include<stdio.h>
#include<algorithm>
#include<vector>
#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], viz[DIM];

void Citire(){
int i, j, 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 Dijkstra( int nodSTART ){
int pas, i, valMIN, nodMIN, vecin, cost;

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

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

        valMIN = INF;

        for(i=1;i<=N;i++)
            if( viz[i] == 0 && valMIN > D[i] ){

                    valMIN = D[i];
                    nodMIN = i;

            }

        viz[nodMIN] = 1;

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

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

            if( viz[ vecin ] == 0 &&  D[vecin] > D[nodMIN] + cost )
                D[vecin] = D[nodMIN] + cost;

        }

    }



    for(i=1;i<=N;i++)
        if( i != nodSTART ){

            if( D[i] ==  INF )
                D[i] = 0;

            fprintf(g,"%d ",D[i]);

        }

}

int main(){

    Citire();
    Dijkstra( 1 );

return 0;
}