//Bellman ford, 25.11.2011
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
const int inf=1000000000;//(~(1<<31));// not 1000....0000 //e prea mare inf+inf ;))
struct nod { int x,y,c; };
vector <nod> v;
int n,m,d[50001];
void citire ()
{
	ifstream fin ("bellmanford.in");
	fin>>n>>m;
	nod t;//t=temp
	t.x=0;t.y=0;t.c=0;
	v.push_back(t);
	for (int i=1;i<=m;i++)
	{
		fin>>t.x>>t.y>>t.c;
		v.push_back(t);
	}
	fin.close();
}
	
bool bellmanford() //return: 1=exista ciclu neg, 0=nu exista
{
	for (int i=2;i<=n;i++) //init, toate distantele sunt inf
		d[i]=inf;
	d[1]=0; //nodul sursa are distanta 0
	
	for (int c=1;c<=n-1;c++) //repetam de (toate nodurile -1) ori
	{	
		for (int i=1;i<=m;i++) //pt fiecare muchie
			if (d[v[i].x]!=inf)
				if (d[v[i].y] > d[v[i].x] + v[i].c) //daca distanta pana la x + distanta dintre x si y e mai mica decat distanta pana la y
					d[v[i].y]=d[v[i].x] + v[i].c; //o punem in vector si continuam....
	}
	
	bool ciclu=0;
	for (int i=1;i<=m;i++) //verificam pt cicluri negative
			if (d[v[i].y] > d[v[i].x] + v[i].c) //daca dupa |v|-1 repetari se mai poate gasi un drum mai scurt
				{ciclu=1; break;} //atunci exista un ciclu negativ
	
	return ciclu;
}
int main ()
{
	citire();
	
	ofstream fout ("bellmanford.out");
	if (bellmanford())
		fout<<"Ciclu negativ!";
	else 
		for (int i=2;i<=n;i++) 
			fout<<d[i]<<" ";
	fout.close();
	return 0;
}