#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define inf 2000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,x,y,z,i,d[50010],v[50010],ciclu[50010];
vector< pair<int,int> > L[50010];
queue<int> q;
int main() {
	fin>>n>>m;
	for (i=1;i<=m;i++) {
		fin>>x>>y>>z;
		L[x].push_back({y,z});
	}
	q.push(1);
	v[1]=1; d[1]=0;
	for (i=2;i<=n;i++)
		d[i]=inf;
	while (!q.empty()) {
		x=q.front();
		q.pop();
		v[x]=0;
		for (i=0;i<L[x].size();i++) {
			y=L[x][i].first;
			int cost=L[x][i].second;
			if (d[y]>d[x]+cost) {
				d[y]=d[x]+cost;
				if (v[y]==0) {
					ciclu[y]++;
					if (ciclu[y]==n) {
						fout<<"Ciclu negativ!";
						return 0;
					}
				}
				q.push(y);
				v[y]=1;
			}
		}
	}
	for (i=2;i<=n;i++)
		fout<<d[i]<<" ";
	return 0;
}