#include <bits/stdc++.h>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");


vector<pair<int,int> > graf[50005];
queue<int> q;
int viz[50005];
int a[50005],fv[50005];
int n,m;
void bellmanford(int sursa)
{
	for(int i=1;i<=n;i++)
		a[i]=INT_MAX-1000;
	a[sursa]=0;
	q.push(sursa);
	while(!q.empty())
	{
		int coada=q.front();
		viz[coada]=0;
		for(int i=0;i<graf[coada].size();i++)
		{
			int vecin=graf[coada][i].first;
			int cost=graf[coada][i].second;
			if(a[vecin]>a[coada]+cost)
			{
				a[vecin]=a[coada]+cost;
				if(viz[vecin]==0)
				{
					viz[vecin]=1;
					fv[vecin]++;
					q.push(vecin);
					if(fv[vecin]==n)
					{
						out<<"Ciclu negativ!";
						return;
					}
				}
			}
		}
		q.pop();
	}
	for(int i=2;i<=n;i++)
		out<<a[i]<<" ";
}
int main()
{
	in>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		in>>x>>y>>c;
		graf[x].push_back({y,c});
	}
	bellmanford(1);
	return 0;
}