#include <fstream>
#include <queue>
#include <vector>
#define push_pair(A,B) push(make_pair(A,B))
using namespace std;

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

struct MUCHIE
{
	int a,b,c;
};

int n,m,i,j,c[50010],nod,next;
long long p;
bool f[50010];
MUCHIE g[250010];
vector<int> v[50010];
priority_queue<pair<int,int> > h;

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
		{in>>g[i].a>>g[i].b>>g[i].c;v[g[i].a].push_back(i);}
	
	for(i=2; i<=n; i++)
		c[i] = 1<<29;
	
	/*for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			if(c[g[j].a] + g[j].c < c[g[j].b])
				c[g[j].b] = c[g[j].a] + g[j].c;*/
	
	h.push_pair(1,1);
	p=0;
	while(!h.empty() && p++<=1LL*n*m)
	{
		nod = h.top().second;
		h.pop();
		f[nod] = 0;
		for(i=0; i<v[nod].size(); i++)
		{
			next = v[nod][i];
			if(c[g[next].a]+g[next].c < c[g[next].b])
			{
				c[g[next].b] = c[g[next].a]+g[next].c;
				if(!f[g[next].b])
				{
					f[g[next].b] = 1;
					h.push_pair(-c[g[next].b], g[next].b);
				}
			}
		}
	}
	
			
	for(i=2; i<=m; i++)
		if(c[g[i].a]+g[i].c < c[g[i].b])
			{out<<"Ciclu negativ!";return 0;}
			
	for(i=2; i<=n; i++)
		out<<c[i]<<' ';
	
	return 0;
}