#include<bits/stdc++.h>
#define f first
#define s second
#define NMAX 50010

using namespace std;

const int inf=1000000000;
int viz[NMAX];
vector<pair<int,int> >V[NMAX];
queue<pair<int,int> >Q;
vector<pair<int,int> >::iterator it;
int n,m;
int x,y,c,cy;
int d[NMAX];

int main() {
	ifstream cin("bellmanford.in");
	ofstream cout("bellmanford.out");
	cin>>n>>m;
	
	for (int i=0; i<m; i++) {
		cin>>x>>y>>c;
		V[x].push_back(make_pair(y,c));
	}
	
	for (int i=1; i<=n; i++) d[i]=inf;
	d[1]=0;
	Q.push(make_pair(1,0));
	while (!Q.empty()) {
		x=Q.front().f;
		c=Q.front().s;
		Q.pop();
		if (d[x]<c) continue;
		
		for (it=V[x].begin(); it!=V[x].end(); it++) {//y- son  cy-cost son
			y=it->f;
			cy=it->s;
			if (d[x]+cy<d[y]) {
				d[y]=d[x]+cy;
				Q.push(make_pair(y,d[y]));
				viz[y]++;
				if (viz[y]==n) {
					cout<<"Ciclu negativ!"; return 0;
				}
			}
		}
	}
	for (int i=2; i<=n; i++) cout<<d[i]<<" ";
	
	
	return 0;
}