#include<bits/stdc++.h>
using namespace std;
long long n,tot,m;
int last[2010];
bool vis[2010];
long long dis[2010];
struct node{
	int next,v,q;
}a[2010];
void add(int x,int y,int w)
{
	tot++;
	a[tot].next=last[x];
	last[x]=tot;
	a[tot].v=y;
	a[tot].q=w;
}
void spfa()
{
	memset(dis,0x7f,sizeof(dis));
	dis[1]=0;
	queue<int>q;
	q.push(1);
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=last[p];i!=-1;i=a[i].next)
		{
			if(dis[a[i].v]>dis[p]+a[i].q)
			{
				dis[a[i].v]=dis[p]+a[i].q;
				if(!vis[a[i].v])
				{
					vis[a[i].v]=1;
					q.push(a[i].v);
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	memset(last,-1,sizeof(last));
	for(int i=0;i<m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	spfa();
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==9187201950435737471)
		{
			cout<<-1;
			continue;
		}
		cout<<dis[i]<<' ';
	}
	return 0;
}

只过了#1，样例过了