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

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

struct edge 
{        
         int v,c;   
         edge(int _v,int _c) : v(_v), c(_c) {} 
};
typedef vector<edge> * graph;


void readGraph(graph &G,int &N,int &M,FILE *fin) { 
 
     fscanf(fin,"%d%d",&N,&M); 
     
     G = new vector<edge>[N];  
     for(int x,y,c,i=0;i<M;++i) { 
          
          fscanf(fin,"%d%d%d",&x,&y,&c); 
          G[--x].push_back(edge(--y,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( vector<edge>::iterator p = G[q].begin(); p != G[q].end(); ++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;
}