#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n,m,i,a,b,c,j,fr[500015],cst[50015],fi,sc;
set<pair<int,int>> ss;
vector<pair<int,int>> veci[50015];

int main() {
	
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b>>c;
		veci[a].push_back(make_pair(b,c));
	}
	ss.insert(make_pair(0,1));
	fr[1]=1;
	bool ciclu=0;
	while(!ss.empty()&&ciclu==0)
	{
		b=(*ss.begin()).first;
		a=(*ss.begin()).second;
		ss.erase(ss.begin());
		
		for(i=0;i<veci[a].size();i++)
		{
			fi=veci[a][i].first;
			sc=veci[a][i].second;
			if(fr[fi]==n+1)	ciclu=1;
			if(b+sc<cst[fi]||fr[fi]==0)
			{
				cst[fi]=b+sc;
				fr[fi]++;
				ss.insert(make_pair(cst[fi],fi));
			}
		}
	}
	if(ciclu==0)
	{
		for(i=2;i<=n;i++)
			fout<<cst[i]<<" ";	cout<<"\n";
	}
	else fout<<"Ciclu negativ!\n";
}