#include <stdio.h>   
#include <stdlib.h>   
#include <string.h>   
#include <vector>   
using namespace std;   
  
typedef vector < pair<int,int> > vii;   
#define INF ~(1<<31)   
#define to first   
#define we second   
#define MINP 1   
#define le(K) (K<<1)   
#define ri(K) ((K<<1) + 1)   
#define fa(K) (K >> 1)   
  
enum {WHITE,GRAY,BLACK};   
const int NMAX = 50000;   
int N,M,d[NMAX],H[NMAX+1],HSZ,pos[NMAX];   
char type[NMAX];   
vii G[NMAX];   
  
void readGraph() {   
        
     freopen("dijkstra.in","r",stdin);   
     scanf("%d%d",&N,&M);   
  
     for(int x,y,w,i=0;i<M;++i) {   
                        
             scanf("%d%d%d",&x,&y,&w);   
             G[--x].push_back(make_pair(--y,w));   
             }       
     }   

inline bool hisempty() {
       return HSZ ? 0 : 1;
}
  
void hswap(int x,int y) {   
     pos[H[x]] = y; pos[H[y]] = x;   
     int aux = H[x]; H[x] = H[y]; H[y] = aux;   
     }   
  
void lift(int K) {   
        
     for(; K > 1 && d[H[K]] < d[H[fa(K)]] ; K = fa(K) )   
           hswap(K,fa(K));   
     }   
  
void dip(int K) {   
        
     int p;   
     for(; ; K = p) {   
                 
              p = K;   
              if(le(K) <= HSZ && d[H[le(K)]] < d[H[p]])   
                       p = le(K);   
              if(ri(K) <= HSZ && d[H[ri(K)]] < d[H[p]])   
                       p = ri(K);   
                 
              if(p != K) hswap(p,K);   
                   else break;   
              }   
     }   
  
int herase(int K) {   
    int sav = H[K];   
    hswap(K,HSZ--);   
    dip(K);   
    return sav;   
}   
  
void hinsert(int v) {   
        
     H[++HSZ] = v; pos[v] = HSZ;   
     lift(HSZ);   
     }   
        
void hupdate(int K) {   
        
     if(K > 1 && d[H[K]] < d[H[fa(K)]])    
       lift(K);   
      else dip(K);   
     }   
  
void dijkstra() {   
  
     for(int i = 0; i < N; ++i)   
      d[i] = INF;   
        
     d[0] = 0; type[0] = GRAY;   
        
     hinsert(0);   
             
     for(int vmin, e = 0;e < N && !hisempty() ; ++e) {   
                
             vmin = herase(MINP);   
             type[vmin] = BLACK;   
                
             for(vii :: iterator it = G[vmin].begin(); it != G[vmin].end(); ++it)   
                       
                     if(type[it->to] != BLACK && d[vmin] + it->we < d[it->to]) {   
                       d[it->to] = d[vmin] + it->we;   
                       if(type[it->to] == WHITE)    
                         type[it->to] = GRAY, hinsert(it->to);   
                        else hupdate(pos[it->to]);   
                     }   
             }   
}   
        
void writeDist() {   
        
     freopen("dijkstra.out","w",stdout);   
     for(int i=1;i<N;++i)   
             printf("%d ",d[i]==INF?0:d[i]);   
     }   
        
int main() {    
    readGraph();   
    dijkstra();   
    writeDist();   
}