#include <cstdio>
#include <cstdlib>
#define NMAX 50001

int N ,M , dist[NMAX] , size , H[NMAX],P[NMAX];
int * G[NMAX] , * C[NMAX];

void readData()
{
 freopen("dijkstra.in","r",stdin);
 scanf("%d %d",&N,&M);
 for(int i = 1; i <= N ; ++i) {
  G[i] = (int*) malloc(sizeof (int) );
  C[i] = (int*) malloc(sizeof (int) );
  G[i][0] = 0;
 }

 for(int i = 0 , x1 , x2 , c; i < M ; ++i) {
  scanf("%d %d %d",&x1,&x2,&c);
   //fprintf(stderr,"%d %d %d \n",x1,x2,c);
  ++G[x1][0];
  G[x1] = (int*) realloc(G[x1], (G[x1][0] + 1) * sizeof (int) );
  C[x1] = (int*) realloc(C[x1], (G[x1][0] + 1) * sizeof (int) );
  G[x1][G[x1][0]] = x2;
  C[x1][G[x1][0]] = c;
 }

 /*
 for(int i = 1; i<=N ; ++i)
  fprintf(stderr,"%d ",G[i][0]);


 for(int i=1;i<=N;++i)
 {
  for(int j = 1 ; j <= G[i][0] ; ++j)
   fprintf(stderr,"%d ",G[i][j]);
  fprintf(stderr,"\n");
 }
 for(int i=1;i<=N;++i)
 {
  for(int j = 1 ; j <= G[i][0] ; ++j)
   fprintf(stderr,"%d ",C[i][j]);
  fprintf(stderr,"\n");
 }  */

}

void swap(int & a, int & b)
{
 int aux = a; a = b; b = aux;
}

void insert(int v)
{
 int slot = !P[v] ? slot = ++size : slot = P[v];
 H[slot] = v;
 while(slot>>1)
 {
  if(dist[H[slot]] < dist[H[slot<<1]])
  {
   swap(H[slot],H[slot<<1]);
   slot>>1;
  }
   else { P[v] = slot; break; }
 }
}

int extract()
{
 int min = H[1], slot = 1;
 P[H[1]] = -1;
 H[1] = H[size--];
 if(size)
  while(true)
  {
   int mins = slot;
   if(slot>>1 <= size & dist[H[slot]] > dist[H[slot>>1]])
     mins = slot >> 1;
    else
     if(slot>>1 + 1 <= size & dist[H[mins]] > dist[H[slot>>1 + 1]])
        mins = slot >> 1 + 1;
     else
        { P[H[slot]] = slot; break; }
   swap(H[slot],H[mins]);
   slot = mins;
  }
 return min;
}

void minPath()
{
 for(int i = 2; i <= N ; ++i)
  dist[i] = 0x7FFFFFFF;
 insert(1);

 while(size)
 {
  int vmin = extract();
  for(int i = 1 ; i <= G[vmin][0] ; ++i)
   if(dist[vmin] + C[vmin][i] < dist[G[vmin][i]])
    {
     dist[G[vmin][i]] = dist[vmin] + C[vmin][i];
     insert(G[vmin][i]);
    }
 }
 }

void writeData()
{
 freopen("dijkstra.out","w",stdout);
 for(int i = 2; i <= N ; ++i)
  printf("%d ",dist[i] < 0x7FFFFFFF ? dist[i] : 0);
}

int main()
{
 readData();
 minPath();
 writeData();
 return 0;
}