#include <cstdio>
#include <cstdlib>

#define NMAX 50001
#define INF 0x7FFFFFFF

int N ,M , dist[NMAX] , K, 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) );
  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;
 }
}

void swap(int x, int y)
{
 P [H[x]] = y; P[H[y]] = x;
 int aux = H[x]; H[x] = H[y]; H[y] = aux;
}

void update(int p)
{
 int pmin = p;
 if( p<<1 <= K & dist[ H[p<<1] ] < dist[ H[p] ] )
   pmin = p << 1;
 if( (p<<1) + 1 <= K & dist[ H[ (p<<1) + 1] ] < dist[ H[pmin] ])
   pmin = (p << 1) + 1;
 if(p != pmin)
   swap(p,pmin), update(pmin);
}

int extract()
{
 int nm = H[1];

 P[ H [1] ] = -1;

 if(K > 1 )
 {
  H[1] = H[K];
  P[ H [1] ] = 1;
 }

 --K;

 update(1);

 return nm;
}

void insert(int nod)
{
 H[++K] = nod;
 P[nod] = K;

 for (int p = K; p>>1 ; p>>=1)
    if(dist[H[p]] < dist[H[p>>1]])
      swap(p , p>>1);
}

void up(int pos)
{
 for(int p = pos; p/2; p/=2)
    if( dist[ H[p]] < dist[H[p>>1] ] )
      swap(p,p>>1);
}


void minPath()
{
 for(int i = 2; i <= N; ++i)
   dist[i] = INF;

 dist[1] = 0;

 insert(1);

 int node;
 while(K)
 {
  node = extract();

  for(int i = 1; i <= G[node][0]; ++i)
     if(dist[node] + C[node][i] < dist[ G[node][i] ])
     {
      dist[ G[node][i] ] = dist[node] + C[node][i];

      if(P[ G[node][i] ]) up(P[ G[node][i] ]);
        else insert(G[node][i]);
     }
 }
}

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

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