#include <bits/stdc++.h>
#define fx first
#define sx second
#define pb push_back
typedef long long ll;
const int Max = 50006;
const int Inf = 2e9;
const int MOD = 666013;
using namespace std;

int n, m, x, y, z, viz[Max], dist[Max];
vector < pair<int,int> > v[Max];
bool ciclu_negativ = false;

void bfs (int start) {
	viz[start] = 1;
	dist[start] = 0;
	queue <int> q;
	q.push(start);
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i=0; i<v[x].size(); i++) {
			if (dist[x] + v[x][i].sx < dist[v[x][i].fx]) {
				if (viz[v[x][i].fx]) {
					ciclu_negativ = true;
				} else {
					viz[v[x][i].fx] = 1;
					dist[v[x][i].fx] = dist[x] + v[x][i].sx;
					q.push(v[x][i].fx);
				}
			}
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	while (m--) {
		cin >> x >> y >> z;
		v[x].pb({y, z});
	}
	for (int i=1; i<=n; i++) dist[i] = 2e9;
	bfs (1);
	if (ciclu_negativ) {
		cout << "Ciclu negativ!\n";
	} else {
		for (int i=2; i<=n; i++) cout << dist[i] << ' ';
		cout << "\n";
	}
	return 0;
}