#include<bits/stdc++.h>
using namespace std;
int h[1000],i,cnt,n,m;//n为点个数，m为边个数 
int que[10000],head=0,tail=1;
int inf=0x7f;
int dis[10000];
struct Edge
{
	int to;
	int next;
	int w;
}edge[100];
void add_Edge(int u,int v,int w)
{
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=h[u];
	h[u]=cnt++;
}
void init()
{
	for(int i=1;i<=n;i++) h[i]=-1;
	cnt=0;	
} 
int main()
{
	int u,v,w; 
	cin >> n >> m;
	init();
	for(i=1;i<=m;i++)
	{
		cin >> u >> v >> w;	
		add_Edge(u,v,w);//链式前向星存图	
	}
	que[1]=1;
	tail++;
	memset(dis,0x7f,sizeof(dis));dis[1]=0;
	while(head<tail)
	{
		for(i=h[que[head]];i!=-1;i=edge[i].next)
		{			
			tail++;
			que[tail]=edge[i].to;
			if(edge[i].w+dis[que[head]]<dis[que[tail]])
				dis[que[tail]]=edge[i].w+dis[que[head]];
		}
		head++;
	}
	for(i=1;i<=n;i++)
		cout << dis[i] << ' ';
	return 0;
}