#include<iostream>
#include<fstream>
#include<vector>
#include<deque>
using namespace std;
const int inf=1000000000;
struct nod { int y,c; };
vector <nod> v[50001];
deque <int> coada;
int n,m,d[50001],apar[50001];
void citire ()
{
	ifstream fin ("bellmanford.in");
	fin>>n>>m;
	
	nod t;
	int x;
	for (int i=1;i<=m;i++)
	{
		fin>>x>>t.y>>t.c;
		v[x].push_back(t);
	}
	fin.close();
}


bool bellmanford() 
{
	for (int i=2;i<=n;i++) 
		d[i]=inf;
	d[1]=0; 
	
	coada.push_back(1);
	while (!coada.empty())
	{		
		int x=coada.front();
		if (d[x]!=inf)
			for (int i=0;i<v[x].size();i++) 
			{
				int y=v[x][i].y;
				int c=v[x][i].c;
				if (d[y] > d[x] + c) 
				{
					d[y] = d[x] + c; 
					coada.push_back(y);
					if ( ++apar[y] > n-1 ) return 1; 
				}
			}
		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;
}