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

#define MAXN 50000
#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<int> vi;
typedef vector<edge> ve;
typedef vector<edge>::iterator pve;
typedef ve graph[MAXN];

void readGraph(graph G,int &N,int &M,FILE *fin) {
     
    fscanf(fin,"%d%d",&N,&M);
    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);
}

vi minDist(graph G,int N,int M,int start) {
   
   queue<int> Q;
   vi d(N,oo);
   vector<bool> inQ(N,false);
   
   d[start] = 0;
   inQ[start] = true;
   Q.push(start);
   
   for(; !Q.empty() ;) {
           
           int q = Q.front();
           for( pve 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(vi d,FILE * fout) {
    
    for(int i=1,n=d.size();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(minDist(G,N,M,0),fopen(FOUT,"w"));
}