#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);
  ++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;
 if(!P[v]) { slot = size + 1; ++size;} else slot = P[v];
 H[slot] = v; P[v] = slot;
 while(slot>>1)
 {
  if(dist[H[slot]] < dist[H[slot>>1]])
  {
   P[H[slot]] = slot>>1; P[H[slot>>1]] = slot;
   swap(H[slot],H[slot>>1]);
   slot>>=1;
  }
   else { P[v] = slot; break; }
 }
}

void update(int poz)
{
 int smin = poz;
 if(poz<<1 <= size & H[poz] > H[poz<<1])
   smin = poz<<1;
 if(poz<<1 + 1 <= size & H[smin] > H[poz<<1 + 1])
   smin = poz<<1 + 1;
 if(smin != poz)
   {
   P[H[poz]] = smin; P[H[smin]] = poz;
   swap(H[poz],H[smin]);
   update(smin);
   }
  else P[H[poz]] = poz;
}

int extract()
{
  int min = H[1]; P[H[1]] = -1;
  H[1] = H[size--];
  if(size > 1) update(1);
  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;
}