#include<cstdio>
const int INF=1e9;
int g[2001][2001];
bool vis[2001];
int dis[2001];
int minn;
int curr;
int n,m;
int min(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) g[i][j]=INF;
		g[i][i]=0;
		dis[i]=INF;
	}
	for(int i=1,u,v,w;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		if(u==v) continue;                       //自环
		else if(g[u][v]) g[u][v]=min(g[u][v],w); //重边
		else g[u][v]=w;
	}
	curr=1;
	dis[curr]=0;
	vis[curr]=true;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			if(g[curr][j]!=INF&&dis[j]>dis[curr]+g[curr][j]&&!vis[j])
				dis[j]=dis[curr]+g[curr][j];
		minn=INF;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&minn>dis[j])
			{
				minn=dis[j];
				curr=j;
			}
		vis[curr]=true;
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==INF) printf("-1 ");
		else printf("%d ",dis[i]);
	}
	return 0;
}