#include <bitset>
#include <queue>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
vector<pair<int,int>> No[50000];
const int inf = 1 << 30;
int d[50001],cnt[50001],N, M;
bitset<50001> v,in;
ifstream f("bellmanford.in");
ofstream of("bellmanford.out");
bool neg=0,semn=0;
void bf(const int& a){
	queue<int> q;
	q.push(a);
	v[a] = 1;
	d[a] = 0;
	while (!q.empty()){
		int x = q.front();
		q.pop();
		in[x] = 0;
		for (auto& j : No[x])
		if (!v[j.first] || d[j.first]>d[x]+j.second){
			v[j.first] = 1;
			d[j.first] = d[x] + j.second;
			++cnt[j.first];
			if (cnt[j.first] > N){
				neg = 1; return;
			}
			if (!in[j.first]) q.push(j.first), in[j.first] = 1;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	N = 0; M = 0;
	string s;
	getline(f, s);
	int j = 0;
	while (s[j] != ' '){
		N = N * 10 + s[j] - '0';
		++j;
	}
	++j;
	while (j < s.size() && s[j] != ' '){
		M = M * 10 + s[j] - '0';
		++j;
	}
	int a, b, c;
	for (int i = 2; i <= N; ++i)
		d[i] = inf;
	for (int i = 0; i < M; ++i){
		j = 0;
		getline(f, s); 
		semn = 0;
		c = 0; b = 0; a = 0;
		while (s[j] != ' '){
			if (s[j] == '-')semn = 1;
			else
			a = a * 10 + s[j] - '0';
			++j;
		}
		if (semn)a *= -1;
		++j;
		semn = 0;
		while (s[j] != ' '){
			if (s[j] == '-')semn = 1;
			else
			b = b * 10 + s[j] - '0';
			++j;
		}
		if (semn)b *= -1;
		++j;
		semn = 0;
		while (j < s.size() && s[j] != ' '){
			if (s[j] == '-')semn = 1;
			else
			c = c * 10 + s[j] - '0';
			++j;
		}
		if (semn)c *= -1;
		No[a].push_back(make_pair(b, c));
	}
	bf(1);
	if (neg)of<<"Ciclu negativ!";
	else
	for (int i = 2; i <= N; ++i)
		of << d[i] << " ";
}