#include<iostream>
#include<fstream>
using namespace std;
struct muchie{int a,b,c;}v[250000];
int d[250000];	
const int inf=0x3f3f3f3f; 

	
int main()
{ifstream f("bellmanford.in");
ofstream h("bellmanford.out");
int n,m,ok,k=0;
f>>n>>m;
for(int i=1;i<=m;i++)
{f>>v[i].a>>v[i].b>>v[i].c;
if(v[i].a==1)
	d[v[i].b]=v[i].c;}
for(int i=2;i<=n;i++)
	if(d[i]==0)
		d[i]=inf;
	do
	{ok=1;
	k++;
		for(int i=1;i<=m;i++)
			if(d[v[i].b]>d[v[i].a]+v[i].c)
				{d[v[i].b]=d[v[i].a]+v[i].c;
	ok=0;}
				}while(ok==0||k>=n);
			if(k>n)
h<<"Ciclu negativ!";
else			
	for(int i=2;i<=n;i++)
	h<<d[i]<<" ";
	return 0;}