#include <stdio.h>

int N, M;
int drum[1000][1000], dist[1000];
int i, j;

int main()
 {
    FILE *f = fopen("dijkstra.in" , "r"), *g = fopen("dijkstra.out" , "w");
    
    fscanf(f , "%d %d" ,&N , &M);
    
    for (i = 1; i <= M; i++)
       {
           int x, y, c;
           fscanf(f , "%d %d %d" , &x , &y , &c);
           drum[x][y] = c;
       }

    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
           if ((drum[i][j] != 0) && ((dist[j] == 0) || (dist[j] > dist[i] + drum[i][j])))  dist[j] = dist[i] + drum[i][j];
           //if (drum[i][j] != 0)
             //     if ((dist[i] == 0) || (dist[i] > dist[j] + drum[i][j])) dist[i] = dist[j] + drum[i][j];

    for (i = 2; i <= N; i++)
      fprintf(g , "%d ", dist[i]);

    
    fclose(f);
    fclose(g);
 
    return 0;
 }