#include<bits/stdc++.h>
using namespace std;
struct node{
	int y,w;
};
const int NN=1e6+10;
int n,m,d[NN],v[NN],ans[NN];
vector<node>e[NN];
void dijkstra()
{
	memset(d,127,sizeof(d));
	d[1]=0;
	priority_queue<pair<int,int>>q;
	q.push({0,1});
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(v[x]) continue;
		v[x]=true;
		for(auto ha:e[x])
		{
			int y=ha.y,w=ha.w;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				q.push({-d[y],y});
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		e[x].push_back(node{y,w});
	}
	dijkstra();
	for(int i=1;i<=n;i++)
	{
		if(d[i]==d[NN-1]) printf("-1 ");
		else printf("%d ",d[i]);
	}
}