#include <fstream>
#include <queue>

using namespace std;
vector <pair<int, int> > v[50005];
priority_queue <pair<int, int> > q;
int best[50005],f[50005];
int main()
{
	ifstream cin("bellmanford.in");
	ofstream cout("bellmanford.out");

	int n,m,a,b,c,ok=0;
	pair<int ,int > pa,ca;
	cin>>n>>m;

	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		pa.second=b;
		pa.first=-c;
		v[a].push_back(pa);
	}
	for(int i=1;i<=n;i++)
	{
		best[i]=-1005;
	}

	pa.second=1;
	pa.first=0;
	q.push(pa);
	best[1]=0;
	while(!q.empty())
	{
		pa=q.top();
		q.pop();
		f[pa.second]++;
		if(f[pa.second]==m)
		{
			ok=1;
			break;
		}
		if(pa.first==best[pa.second])
		{
			for(int i=0;i<v[pa.second].size();i++)
			{
				ca.second=v[pa.second][i].second;
				ca.first=v[pa.second][i].first+pa.first;
				if(ca.first>best[ca.second])
				{
					best[ca.second]=ca.first;
					q.push(ca);
				}
			}
		}
	}

	if(ok==1)
	{
		cout<<"Ciclu negativ!";
	}
	else
	{
		for(int i=2;i<=n;i++)
		{
			cout<<best[i]*(-1)<<" ";
		}
	}

    return 0;
}