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

using namespace std;

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

#define NMax 50005
#define inf (1 << 30) - 1
#define pii pair<int, int>

int n, m;
vector< pii > G[NMax];
int d[NMax], nr[NMax];
bitset<NMax> inq;

void init();
void rezolvare();

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

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

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