//Bellman-Ford O(M*N)

#include<stdio.h>
#define Nmax 250005
#define inf 100000000

int x[Nmax], y[Nmax], d[Nmax];
int dist[50005];

int main(){

    FILE *fin = fopen("dijkstra.in","r"),
         *fout = fopen("dijkstra.out","w");
         
    int N,M;
    fscanf(fin,"%d%d",&N,&M);
    
    for(int i=1;i<=M;i++)
        fscanf(fin,"%d%d%d",&x[i],&y[i],&d[i]);
        
    for(int i=1;i<=N;i++) 
        dist[i]=inf;
    dist[1]=0;
    
    for(int i=1;i<=N;i++){
        char flag = 0;
        
        for(int j=1;j<=M;j++)
            if(dist[y[j]] > dist[x[j]] + d[j]){
                dist[y[j]] = dist[x[j]] + d[j];
                flag = 1;
            }
        
        if(!flag)
            break;                    
    }
        
    for(int i=2;i<=N;i++)
        if(dist[i] < inf)
            fprintf(fout,"%d ",dist[i]);
        else
            fprintf(fout,"0 ");
        
    fclose(fin);
    fclose(fout);
    return 0;
}