#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
#define maxn 50001
#define pb push_back
vector <int> vec[maxn];
vector <int> cost[maxn];
vector <int> q;
int d[50001];
bool este[maxn];
int cate[maxn];
int n,m;
int main(){
	ifstream fi("bellmanford.in");
	ofstream g("bellmanford.out");
	fi>>n>>m;
	int i,j;
	for(i=1;i<=m;i++){
		int a,b,c;
		fi>>a>>b>>c;
		vec[a].pb(b);
		cost[a].pb(c);
		
		if(i<=n)
			d[i]=100000;
	}
	d[1]=0;
	q.pb(1);
	este[1]=true;
	int f=0,l=0;
	while(f<=l){
		int nod=q[f];
		for(i=0;i<vec[nod].size();i++){
			if(d[vec[nod][i]]>d[nod]+cost[nod][i]){
				d[vec[nod][i]]=d[nod]+cost[nod][i];
				if(este[vec[nod][i]]==false){
					q.pb(vec[nod][i]);
					l++;
					este[vec[nod][i]]=true;
					cate[vec[nod][i]]++;
				}
			}
		}
		if(cate[nod]>n){
			g<<"Ciclu negativ!";
			return 0;
		}
		este[nod]=false;
		f++;
	}	
	for(i=2;i<=n;i++){
		g<<d[i]<<" ";
	}
	return 0;
}