#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const unsigned int inf = (1 << 30) - 1;

#define mp make_pair

#define NMax 50010
#define MMax 250010

int n, m;
vector< pair<int, int> > G[NMax];
int d[NMax];
queue<int> q;
vector<bool> inq(NMax, false);
int nr[NMax];

void init();
void rezolvare();

int main(){
	init();
	rezolvare();
}

void init(){
	int i;
	int x, y, c;
	fin >> n >> m;
	for(i = 0; i < m; i++){
		fin >> x >> y >> c;
		G[x].push_back(mp(y, c));
	}
	for(i = 2; i <= n; i++){
		d[i] = inf;
	}
}

void rezolvare(){
	int i, x, v;
	bool negativ = false;
	q.push(1);
	while(q.size() && !negativ){
		x = q.front(); q.pop();
		inq[x] = false;
		for(i = 0; i < G[x].size(); i++){
			v = G[x][i].first;
			if(d[v] > d[x] + G[x][i].second){
				d[v] = d[x] + G[x][i].second;
				nr[v]++;
				if(nr[v] > n) negativ = true;
				if(!inq[v]){
					q.push(v);
					inq[v] = true;
				}
			}
		}
	}
	if(negativ) fout << "Ciclu negativ!";
	else for(i = 2; i <= n; i++) fout << d[i] << ' ';
}