#include <stdio.h>
#include <vector>
#include <queue>
#define size 50100;
#define max 2000000000;

typedef struct a{
	long x,t;
	} adat;

long i,j,n,m,u,p;
adat a;
vector<adat> v[size];
vector<int> dist;

struct comp{
    int operator()(long x, long y) { return dist[x]>dist[y] ? 1 : 0; }
	};

int main()
{
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 
 scanf("%d %d",&n,&m);
 for(i=1;i<=n;++i){
	 for(j=1;j<=m;++j){
		scanf("%d %d %d",p,a.x,a.t);
		v[p].push_back(a);
	 }
	 scanf("\n");
 }
	
 priority_queue<int, vector<int>, comp> heap;
 
 for(i=1;i<=n;++i) dist[i]=max;
 heap.push(1);
 dist[1]=0;
 while(!heap.empty()){
	u=heap.top();
	heap.pop();
	for(i=0;i<=v[u].size();++i){
	  if(dist[v[u][i].x]>dist[u]+v[u][i].t){
		 dist[v[u][i].x]=dist[u]+v[u][i].t;
		 heap.push(v[u][i].x); 
		  }	
	} 
	 
 }	
	
 for(i=2;i<=n;++i){
	 if(dist[i]==max) printf("#c ","0") else
	 printf("%d ",dist[i]);
	 }	

 return 0;

}