//Bellman ford, 25.11.2011
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
const int inf=(~(1<<31));// not 1000....0000
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=0;i<=m;i++) //init, toate distantele sunt inf
		d[i]=inf;
	d[1]=0; //nodul sursa are distanta 0
	
	for (int c=1;c<m;c++) //repetam de (toate nodurile -1) ori
		for (int i=1;i<=m;i++) //pt fiecare muchie
			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]<<' ';
		
	return 0;
}