#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;

typedef vector < pair<int,int> > vii;
#define INF 0x7f7f7f7f
#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));
             }    
     }

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() {

     memset(d,0x7f,sizeof d);
     
     d[0] = 0; type[0] = GRAY;
     
     hinsert(0);
          
     for(int vmin,e=0;e<N;++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]);
     }
     
int main() { 
    readGraph();
    dijkstra();
    writeDist();
}