#include<cstdio>
#define N 501
#define M 25001
#define INF (1<<31)-1
int *a[N],*a1[N],x[M],y[M],c[M],n,m,cost[N];
bool viz[N];
void citire()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&x[i],&y[i],&c[i]);
		++cost[x[i]];
	}
	for (int i=1;i<=n; ++i)
	{
		a[i]=new int [1+cost[i]];
		a[i][0]=0;
		a1[i]=new int [1+cost[i]];
		a1[i][0]=0;
	}
	for (int i=1; i<=m; ++i)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		a1[x[i]][++a1[x[i]][0]]=c[i];
	}
}
void initializare()
{
	cost[1]=0;
	for (int i=2; i<=n; ++i)
		cost[i]=INF;
}
void bf(int x0)
{
	int coada[M],x,y,u=0,p=0;
	coada[u++]=x0;
	viz[x0]=true;
	while (p!=u)
	{
		x=coada[p++];
		viz[x]=false;
		for (int i=1; i<=a[x][0]; ++i)
		{
			y=a[x][i];
			if (cost[y]>cost[x]+a1[x][i])
			{
				cost[y]=cost[x]+a1[x][i];
				if (!viz[y])
				{
					viz[y]=true;
					coada[u++]=y;
				}
			}
		}
	}
}
bool ciclu_negativ()
{
	for (int i=1; i<=m; ++i)
		if (cost[x[i]]+c[i]<cost[y[i]])
			return true;
	return false;
}
void afis()
{
	for (int i=2; i<=n; ++i)
		printf("%d ",cost[i]);
}
int main()
{
	citire();
	initializare();
	bf(1);
	if (ciclu_negativ())
		printf("ciclu negativ");
	else
		afis();
	return 0;
}