#include<cstdio>
#define N 50001
using namespace std;
#include<vector>
int x,y,z,n,m;
#define inf 1<<30
#define pb push_back
#include<bitset>
#include<queue>
vector<int>a[N],c[N],dist(N,inf),nr(N,0);
bitset<N>viz;
queue<int>coada;
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,&y,&z);
		a[x].pb(y);
		c[x].pb(z);
	}
}
bool bf()
{
	int p=0,u=0;
	coada.push(1);
	++u;
	viz[1]=1;
	dist[1]=0;
	while (p!=u)
	{
		x=coada.front();
		++p;
		coada.pop();
		viz[x]=0;
		size_t g=a[x].size();
		for (size_t i=0; i<g; ++i)
		{
			y=a[x][i];
			if (dist[x]==inf) continue;
			if (dist[y]>dist[x]+c[x][i])
			{
				dist[y]=dist[x]+c[x][i];
				if (!viz[y])
				{
					++nr[y];
					if (nr[y]>n)
						return true;
					viz[y]=1;
					coada.push(y);
					++u;
				}
			}
		}
	}
	return false;
}
int main()
{
	citire();
	if (bf())
		printf("ciclu negativ");
	else
		for (int i=2; i<=n; ++i)
			printf("%d ",dist[i]);
	return 0;
}