#include <bits/stdc++.h>
using namespace std;
int i,j,n,m,a,b,w;
vector <int> dist;
vector <pair<int,int> > graf[50005];
bool neg_cycle;
//ifstream  in("bellmanford.in");
//ofstream  out("bellmanford.out");

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	cin >> n >> m ;
	dist.resize(n+2);
	for (i=1;i<=m;i++)
	{
		cin >> a >>b >> w ;
		graf[a].push_back({b,w});
	}
	for (i=1;i<=n;i++)
	{
		dist[i]=INT_MAX;
	}
	dist[1]=0;
	for (i=1;i<=n-1;i++)
	{
		for (j=1;j<=n;j++)
		{
			for (auto e:graf[j])
			{
				a=j;
				b=e.first;
				w=e.second;
				if (dist[a]<INT_MAX)dist[b]=min(dist[b],dist[a]+w);
			}
		}
	}
	neg_cycle=false;
		for (j=1;j<=n;j++)
		{
			for (auto e:graf[j])
			{
				a=j;
				b=e.first;
				w=e.second;
				if (dist[a]+w<dist[b] && dist[a]<INT_MAX)neg_cycle=true; 
			}
		}
	if (neg_cycle==true)cout <<"Ciclu negativ!\n";
	else 
	{
		for (i=2;i<=n;i++)
		{
			cout << dist[i]<<" ";
		}
	}
    return 0;
}