#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,dist[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++)
		dist[i]=inf;
	dist[1]=0;
	coada.push_back(1);
	while(!coada.empty()){
		int x=coada.front();
		if(dist[x]!=inf)
			for(int i=0;i<v[x].size();i++){
				int vecin=v[x][i].y;
				int cost=v[x][i].c;
				if(dist[vecin]>dist[x]+cost){
					dist[vecin]=dist[x]+cost;
					coada.push_back(vecin);
					if(++apar[vecin]>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<<dist[i]<<" ";
	g.close();
	return 0;
}