#include <stdio.h>
#define NMAX 50001


const int inf = 1 << 30;


struct graf{
    int vf, cost;
    graf *next;
    };

graf *a[NMAX];
int dist[NMAX], vizitat[NMAX];

int N, M;
int i, j;
int min = 0, poz = 1;



int add(int x, int y, int c)
  {
   graf *p = new graf;
   p -> vf = y;
   p -> cost = c;
   p -> next = a[x];
   a[x] = p;
   }


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);
           add(x,y,c);
       }

    for (i = 2; i <= N; i++)
       dist[i] = inf;


    vizitat[1] = 1;
    for (i = 1; i <= N; i++)
       {
          min = inf;
          for (j = 1; j <= N; j++)
             if ((dist[j] < min) && (!vizitat[j]))
                   min = dist[j], poz = j;

          vizitat[poz] = 1;

          graf *p = a[poz];

          while (p)
            {
              if (dist[p -> vf] > dist[poz] + p -> cost)
                    dist[p -> vf] = dist[poz] + p -> cost;
              p = p -> next;
            }

       }



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


    fclose(f);
    fclose(g);

    return 0;
 }