#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct muchie
{
	int d,cost;
};

const int inf=1<<30;
const int N=50006;
vector<muchie> a[N];
int dist[N];
int use[N];
queue <int> q;
int n,m;

int bf(int x)
{
	dist[x]=0;
	q.push(x);
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		use[x]++;
		if(use[x]==n)
			return 0;
		for(vector<muchie> :: iterator i=a[x].begin(); i!=a[x].end();i++)
		{
			if(dist[(*i).d]>dist[x]+(*i).cost)
			{
				dist[(*i).d]=dist[x]+(*i).cost;
				q.push((*i).d);
			}
		}
	}
	return 1;
}
	
int main()
{
	int x,y,c,i;
	in>>n>>m;
	while(m--)
	{
		in>>x>>y>>c;
		a[x].push_back((muchie){y,c});
	}
	for(i=1;i<=n;i++)
		dist[i]=inf;
	if(bf(1)==0)
		out<<"Ciclu negativ!";
	else
	{
		for(i=2;i<=n;i++)
			out<<dist[i]<<" ";
	}
	out<<"\n";
	
	return 0;
}