#include<iostream>
#include<fstream>
#include<vector>
#include<deque>
using namespace std;
const int inf=0xfffffff;
struct nod{
	int y,c;
};
vector <nod> v[50001];
deque <int> coada;
int n,m,d[50001],apar[50001];
void citire(){
	ifstream f("bellmanford.in");
	f>>n>>m;
	int x;
	nod t;
	for(int i=1;i<=m;i++){
		f>>x>>t.y>>t.c;
		v[x].push_back(t);
	}
	f.close();
}
bool bellmanford(){
	for(int i=2;i<=n;i++){
		d[i]=inf;
		apar[i]=0;
	}
	d[1]=0;
	coada.push_back(1);
	apar[1]=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);
					apar[y]++;
					if(apar[y]>n-1)return 1;
				}
			}
			coada.pop_front();
	}
	return 0;
}
int main(){
	citire();
	ofstream g("bellmanford.out");
	if(bellmanford())
		g<<"Ciclu negativ!"<<endl;
	else
		for(int i=2;i<=n;i++)
			g<<d[i]<<" ";
	g.close();
	return 0;
}