#include <stdio.h>

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

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 (j < i)
                                for (k = 1; k <= N; k++)
                                     if ((drum[j][k] != 0) && (dist[k] > dist[j] + drum[j][k]))
                                             dist[k] = dist[j] + drum[j][k];
                         }
           //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;
 }