#include <stdio.h>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const long size = 50100;
const long maxi = 2000000000;
long n,m,i,u,x,y,t;
long dist[size];

struct nod{
 long csp,ta;
};

vector<nod> v[size];
vector<nod>::iterator q;
nod adat;

struct comp
{
  bool operator() (long a, long b) { return dist[a]<dist[b]; }     
};

int main()
{
 //freopen("dijkstra.in","r",stdin);
 //freopen("dijkstra.out","w",stdout); 
 ifstream f("dijkstra.in");
 ofstream g("dijkstra.out");
 
 //scanf("%ld %ld\n",&n,&m);
 f >> n>>m;
 for(i=1;i<=m;++i){
   //scanf("%ld %ld %ld\n",&x,&y,&t);
   f >> x>>y>>t;
   adat.csp=y;
   adat.ta=t;
   v[x].push_back(adat);                
 }                 
 
 priority_queue<long, vector<long>, comp> heap;
 
 for(i=1;i<=n;++i) dist[i]=maxi;
 dist[1]=0;
 heap.push(1);

 while(!heap.empty()){
  u=heap.top();
  heap.pop();
  for(q=v[u].begin(); q<v[u].end(); ++q){
   if(dist[q->csp]>dist[u]+q->ta){
      dist[q->csp]=dist[u]+q->ta;
      heap.push(q->csp);                              
   }             
  } 
 }   
 
 for(i=2;i<=n;++i){
    if(dist[i]==maxi) //printf("0 ");  
    g << "0 ";
    else //printf("%ld ",dist[i]); 
    g << dist[i] << " "; 
 }   
 
 return 0;
}