#include<bits/stdc++.h>
#define x first
#define y second
#define NMAX 50010
using namespace std;

const int inf=1e9;
int n,m;
vector<pair<int,int> >V[NMAX];
int u[NMAX];
bool inQ[NMAX];
queue<int>Q;
int d[NMAX];

int main() {
	ifstream cin("bellmanford.in");
	ofstream cout("bellmanford.out");
	cin>>n>>m;
	
	for (int i=0; i<m; i++) {
		int x,y,c; cin>>x>>y>>c; V[x].push_back({y,c});
	}
	
	for (int i=2; i<=n; i++) d[i]=inf;
	Q.push(1);
	while (!Q.empty()) {
		int x=Q.front();
		Q.pop(); inQ[x]=0;
		
		for (int i=0; i<V[x].size(); i++) {
			int y=V[x][i].x;
			int cy=V[x][i].y;
			if (d[y]>d[x]+cy) {
				d[y]=d[x]+cy;
				Q.push(y);
				if (!inQ[x]) inQ[x]=1, u[y]++;
				if (u[y]==n) {
					cout<<"Ciclu negativ!"; return 0;
				}
			}
		}
	}
	
	for (int i=2; i<=n; i++) cout<<d[i]<<" ";
	return 0;
}