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

using namespace std;

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

vector < pair<int,int> > G[NMAX];

void readData()
{
 freopen("dijkstra.in","r",stdin);
 scanf("%d %d",&N,&M);

 for(int i = 0 , x1 , x2 , c ; i < M ; ++i)
 {
  scanf("%d %d %d",&x1,&x2,&c);
  G[x1].push_back(make_pair(x2,c));
 }

 /*
 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;
 } */
 /*
 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 x)
{
 int poz;
 if(!P[x]) poz = (++size), H[poz] = x , P[x] = poz;
  else poz = P[x];

 while(poz>>1 & dist[H[poz]] < dist[H[poz>>1]])
 {
  swap(P[H[poz]],P[H[poz>>1]]); swap(H[poz],H[poz>>1]);
  poz>>=1;
 }
}

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

int extract()
{
 int min = H[1];
 P[H[1]] = -1;
 H[1] = H[size--]; P[H[1]] = 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(vector< pair<int,int> > :: iterator it = G[vmin].begin() ; it != G[vmin].end() ; ++it)
   if(dist[vmin] + it->second < dist[it->first])
    {
     dist[it->first] = dist[vmin] + it->second;
     insert(it->first);
    }
 }
 }

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;
}