#include <queue>
#include <vector>
using namespace std;

#define MAXN 50000
#define MAXE 250000
#define oo 0x7FFFFFFF
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"

typedef struct edge
{
        int v,c;
        edge(int _v,int _c) : v(_v), c(_c) {}
} * graph[MAXN];
struct e{int x,y,c;};

void readGraph(graph &G,int &n,int &m,FILE * fin) {

     vector<int> deg(MAXN,0);
     vector< e > edg(MAXE);
     
     fscanf(fin,"%d%d",&n,&m);
     for(int i = 0 ; i < m ; ++i) {

             fscanf(fin,"%d%d%d",&edg[i].x,&edg[i].y,&edg[i].c);
             -- edg[i].x; -- edg[i].y;
             deg[ edg[i].x ] ++;
     }
     
     for(int i = 0 ; i < n ; deg[i++] = 0) {
             
                     G[i] = (edge*)calloc(deg[i] + 1,sizeof(edge));
                     G[i][ deg[i] ] = edge(-1,-1);
     }
     for(int i = 0; i < m; ++i)            {
           G[ edg[i].x ] [ deg[ edg[i] . x ] ++ ] = edge(edg[i] . y, edg[i] . c);
     }   
     fclose(fin);
}

int * getMinDist(graph G,int N,int start) {
   
   queue<int> Q;
   vector<bool> inQ(N,false);
   int * d = (int*)calloc(N,sizeof(int));
   
   for(int i = 0 ; i < N; d[i++] = oo);
   d[start] = 0;
   inQ[start] = true;
   Q.push(start);
   
   for(; !Q.empty() ;) {
           
           int q = Q.front();
           for( edge * p = G[q]; p->v != -1; ++p )
           if(d[p->v] > d[q] + p->c) {
                      
                      d[p->v] = d[q] + p->c;
                      if(!inQ[p->v]) {
                                     Q.push(p->v);
                                     inQ[p->v] = true;
                      }
           }
           Q.pop(); inQ[q] = false;
   }
   return d;
}

void writeSol(int * d,int N,FILE * fout) {
    
    for(int i=1;i<N;++i) {
            fprintf(fout,"%d ",d[i]==oo?0:d[i]);
    }
    fclose(fout);
}

int main() {
    
    graph G;
    int N,M;
    readGraph(G,N,M,fopen(FIN,"r"));
    
    writeSol(getMinDist(G,N,0),N,fopen(FOUT,"w"));
    return 0;
}