#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define nmax 50010
#define inf 1<<30

vector <pair<int, int> > v[nmax];
queue <int> q;
int n, m, in[nmax], cin[nmax], cost[nmax];

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i, x, y, c;
	for (i=1; i<=m; i++) 
	{
		scanf("%d %d %d",&x, &y, &c);
		v[x].push_back(make_pair(y,c));
	}
	
	int ciclu=0;
	for (i=2; i<=n; i++) cost[i]=inf;
	q.push(1);
	while (!q.empty() && !ciclu)
	{
		x=q.front();
		q.pop();
		in[x]=0;
		cin[x]=1;
		for (i=0; i<v[x].size(); i++)
		{
			y=v[x][i].first;
			c=v[x][i].second;
			if (cost[x]+c<cost[y])
			{
				cost[y]=cost[x]+c;
				if (!in[y])
				{
					q.push(y);
					in[y]=1;
					cin[y]++;
					if (cin[y]>n) 
					{
						ciclu=1;
						break;
					}
				}
			}
		}
	}
	
	if (ciclu) printf("Ciclu negativ"); else
		for (i=2; i<=n; i++) printf("%d ",cost[i]);
}