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

using namespace std;

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

struct nod{
 long csp,ta;
 nod * kov;
};

nod * v[size], * q;

int add(int k, long h, long ut)
{
 nod * p = new nod;
 p->csp=h;
 p->ta=ut;
 p->kov=v[k];
 v[k]=p;
 return 0;
}

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); 
 
 for(i=1;i<=n;++i) v[i]=NULL;
 scanf("%ld %dl",&n,&m);
 for(i=1;i<=n;++i){
   for(j=1;j<=m;++j){
     scanf("%ld %ld %ld",&x,&y,&t);
     add(x,y,t);                
   }                 
   scanf("\n");
 }
 
 priority_queue<long, vector<long>, comp> heap;
 
 for(i=1;i<=n;++i) dist[i]= maxi;
 heap.push(1);
 dist[1]=0;
 
 while(!heap.empty()){
  u=heap.top();
  heap.pop();
  q=v[u];
  while(q!=NULL){
   if(dist[q->csp]>dist[u]+q->ta){
     dist[q->csp]=dist[u]+q->ta;
     heap.push(q->csp);                              
   }              
   q=q->kov;
  }
 }
 
 for(i=2;i<=n;++i){
    if(dist[i]==maxi){ printf("0 "); } 
    else
    { printf("%ld ",dist[i]); }
 }   
 
 return 0;
}