#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <fstream>
#include <map>
using namespace std;
#define MAX 1000001
#define inf 0xfffffff

int n, m, d[50005];

vector<pair<int,int> > gr[50005];
set<int> q[2];

void bford() {
	int a = 1, b = 0, x, y, c;
	for (int i = 1; i <= n; i++) d[i] = inf;
	d[1] = 0;
	q[0].insert(1);
	for (int i = 1; i < n; i++) {
		a = a^1;
		b = b^1;
		while (q[a].size()){
			x = *q[a].begin();
			q[a].erase(q[a].begin());
			for (int i = 0; i < gr[x].size(); i++) {
				y = gr[x][i].first;
				c = gr[x][i].second;
				if (d[y] > d[x] + c) {
					d[y] = d[x] + c;
					q[b].insert(y);
				}
			}
		}
	}
	if (q[a].size() > 0 || q[b].size() > 0) {
		printf("Ciclu negativ!\n");
	} else {
		for (int i = 2; i <= n; i++) printf("%d ", d[i]);
	}
}

int main() {
	int x,y,c;
	
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &c);
		gr[x].push_back(make_pair(y,c));
	}
	
	bford();
	
	return 0;
}