//Bellman ford eficient: verificam doar vecinii nodurilor cu distante mai bune, 26.11.2011
#include<iostream>
#include<fstream>
#include<vector>
#include<deque>
using namespace std;
const int inf=1000000000;
struct nod { int y,c; };//y=vecin, c=cost
vector <nod> v[50001];
deque <int> coada;
int n,m,d[50001],apar[50001];//d tine distantele, apar - nr de intrari in coada
void citire ()
{
	ifstream fin ("grader_test18.in");
	fin>>n>>m;
	
	nod t;//temp
	int x;
	for (int i=1;i<=m;i++)
	{
		fin>>x>>t.y>>t.c;
		v[x].push_back(t);
	}
	fin.close();
}
/*debug*/void afi(){cout<<"\nCoada: "; for (int i=0;i<coada.size();i++) cout<<coada[i]<<' ';}

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
	
	coada.push_back(1);
	while (!coada.empty())
	{		
		int x=coada.front();//x=vf curent
		if (d[x]!=inf) //daca distanta pana la el a fost modificata (altfel n-are rost sa continuam, ea fiind inf)
			for (int i=0;i<v[x].size();i++) //pt fiecare vecin al nodului curent
			{
				int y=v[x][i].y;//y=vecinul lui x
				int c=v[x][i].c;//c=costul dintre x si y
				if (d[y] > d[x] + c) //daca distanta pana la x + distanta dintre x si y e mai mica decat distanta pana la y
				{
					d[y] = d[x] + c; //o modificam
					coada.push_back(y);//si-l punem in coada
					if ( ++apar[y] > n-1 ) return 1; //daca nodul introdus in coada a fost introdus de n-1 ori atunci avem ciclu negativ
				}
			}
		coada.pop_front();
	}
	return 0;
}
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;
}