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

#define oo 2147483647

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

struct nod
{	int to,cost;
	nod(int y,int c)
	{	to = y; cost = c;
	}
};
typedef vector<nod>:: iterator it;

int N,M;
int d[50001];
int nr[50001];
vector<nod>a[50001];
bitset<50001>in;
queue<int>q;

bool BF()
{	int x;
	q.push(1); d[1] = 0; nr[1] = 1; in[1] = 1;
	while(!q.empty())
	{	x = q.front(); q.pop(); in[x] = 0;
		for(it i = a[x].begin(); i != a[x].end(); i++)
		{	if(d[i->to] > d[x] + i->cost)
				d[i->to] = d[x] + i->cost;
			if(!in[i->to]) q.push(i->to) , in[i->to] = 1 , nr[i->to]++;
			if(nr[i->to] >= N)
				return 0;
		}
	}
	return 1;
}

int main()
{	int i,j,x,y,c;
	f>>N>>M;
	for(i = 1; i <= M; i++)
	{	f>>x>>y>>c;
		a[x].push_back(nod(y,c));
	}
	for(i = 1; i <= N; d[i++] = oo); 
	if(BF())
		for(i = 2; i <= N; i++) g<<d[i]<<" ";
	else g<<"Ciclu negativ!";
	f.close();
	g.close();
	return 0;
}