#include <bits/stdc++.h>
using namespace std;
int i,n,m,a,b,w;
vector <int> dist;
tuple <int,int,int> muchie;
vector <tuple <int,int,int> > edges;
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 ;
		muchie=make_tuple(a,b,w);
		edges.push_back(muchie);
	}
	for (i=1;i<=n;i++)
	{
		dist[i]=INT_MAX;
	}
	dist[1]=0;
	for (i=1;i<=n-1;i++)
	{
		for (auto e:edges)
		{
			tie(a,b,w)=e;
			dist[b]=min(dist[b],dist[a]+w);
		}
	}
	neg_cycle=false;
	for (auto e:edges)
		{
			tie(a,b,w)=e;
			if (dist[a]+w<dist[b])neg_cycle=true;
		}
	if (neg_cycle)cout <<"Ciclu negativ!\n";
	else 
	{
		for (i=2;i<=n;i++)
		{
			cout << dist[i]<<" ";
		}
	}
    return 0;
}