#include <bits/stdc++.h>
using namespace std;
//queue<int> q;
int dis[1000001],head[1000001],low[1000001],vis[1000001],color[1000001];
int n,m,cnt,color_num/*,x,y*/;
struct edge{
	int to,next,w;
}e[1000001];
void addedge(int x,int y,int z){
	e[++cnt].to=y;
	e[cnt].w=z;
	e[cnt].next=head[x];
	head[x]=cnt;
	return;
}
void spfa(int S){
	queue<int> q;
	for(int i=1;i<=n;i++){
		dis[i]=10290140;
		vis[i]=0;
	}
	dis[S]=0;
	vis[S]=1;
	q.push(S);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].to){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return;
}
//int z;
int main(){
	cin>>n>>m;
	int x,y,z;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
//		cout<<i<<endl;
		addedge(x,y,z);
	}
	spfa(1);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
}
/*
6 8
1 3 1
3 5 1
1 2 1
2 4 1
4 1 1
3 4 1
4 6 1
5 6 1
*/

搞完死去的算法就睡觉QAQ