#include <queue>
#include<stdio.h>
using namespace std;
const int inf = 1 << 30;
long d[100000],n,m,s;
int incoada[100000];
struct muchie
{
     long vf;
    long cost;
};

vector<muchie> l[100000]; 
int main(){
     FILE *f;
     long i,x,y,cost;
     queue<long> c;
     f=fopen("dijkstra.in","r");
     fscanf(f,"%ld %ld",&n,&m);
     for(i=0;i<m;i++){
         fscanf(f,"%ld %ld %ld",&x,&y, &cost);
         muchie m;
         m.vf=y-1;
         m.cost=cost;
         l[x-1].push_back(m);
     }
     fclose(f);
     for(i=0;i<n;i++)
        d[i]=inf;
     
     c.push(0);
     d[0]=0;
     incoada[0]=1;
     while(c.size()>0){
         x=c.front();
         c.pop();
         incoada[x]=0;
         for(i=0;i<l[x].size();i++){
               if(d[x]+l[x][i].cost<d[l[x][i].vf]){
                  d[l[x][i].vf]=d[x]+l[x][i].cost;
                  if(incoada[l[x][i].vf]==0){
                      c.push( l[x][i].vf);
                      incoada[l[x][i].vf]=1;
                  }
                  
              } 
         }     
     }      
     
            
    f=fopen("dijkstra.out","w");                   
    for (i = 1; i <n; ++i )
      fprintf(f, "%ld ", (d[i] == inf) ? 0 : d[i]);

    fclose(f);   
    return 0;   
}