#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

#define MN (50001)
#define INF (50000001) // MN*1000+1 with 1000 being the maximum cost of an edge

int N, M, d[MN];
vector< pair<int, int> > g[MN];
bool v[MN]; // true if node i is in the queue
int cntv[MN]; // how many times node i has been in the queue
queue<int> q;

bool bellman_ford(int snode)
{
	int i, n1, n2, c;
	vector< pair<int, int> >::iterator it;
	for(i = 0; i < N; ++i) {
		d[i] = INF;
		v[i] = false;
		cntv[i] = 0;
	}
	d[snode] = 0; v[snode] = true; cntv[snode] = 1; q.push(snode);
	for(; !q.empty(); q.pop()) {
		v[n1 = q.front()] = false;
		//printf("Using d[%d] = %d\n", n1, d[n1]);
		for(it = g[n1].begin(); it != g[n1].end(); ++it) {
			n2 = it->first; c = it->second;
			if(d[n1]+c < d[n2]) {
				d[n2] = d[n1]+c;
				if(!v[n2]) {
					if(cntv[n2] > N)
						return true;
					q.push(n2);
					v[n2] = true;
					++cntv[n2];
				}
			}
		}
	}
	return false;
}

int main()
{
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	
	int i, A, B, C;

	scanf("%d %d", &N, &M);

	for(i = 0; i < M; ++i) {
		scanf("%d %d %d", &A, &B, &C); --A; --B;
		g[A].push_back(make_pair(B, C));
	}

	if(!bellman_ford(0)) {
		for(i = 1; i < N; ++i)
			printf("%d ", d[i] == INF? 0 : d[i]);
	} else printf("Ciclu negativ!\n");

	return 0;
}