#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <iterator>
#include <bitset>
#include <queue>
#include <functional>
#include <utility>
#define MAXN 1002
#define INF 1000000

using namespace std;

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

typedef pair < int, int > pii;
vector<pii> adj[50001];
vector<int> adj_t[50001];

int main() {
	ios::sync_with_stdio(false);
	int n, m, i, x, y, c;

	fin >> n >> m;

	for (i = 0; i < m; ++i) {
		fin >> x >> y >> c;
		adj[x].push_back({ y, c });
		adj_t[x].push_back(y);
	}

	queue<int> Q;
	bitset<50001> inQ;
	vector<int> dist(50001, INF), cntInQ(50001, 0);
	bool negativeCycle = false;

	dist[1] = 0;
	inQ[i].flip();
	Q.push(1);
	while (!Q.empty() && !negativeCycle) {
		x = Q.front();
		Q.pop();

		inQ[x] = false;

		for (i = 0; i < adj[x].size(); ++i) {
			if (dist[adj[x][i].first] > dist[x] + adj[x][i].second) {
				dist[adj[x][i].first] = dist[x] + adj[x][i].second;

				if (!inQ[adj[x][i].first]) {
					if (cntInQ[adj[x][i].first] > n)
						negativeCycle = true;
					else {
						Q.push(adj[x][i].first);
						inQ[adj[x][i].first] = true;
						++cntInQ[adj[x][i].first];
					}
				}
			}
		}
	}

	if (negativeCycle == true)
		fout << "Ciclu negativ!";
	else {
		for (i = 2; i <= n; ++i)
			fout << dist[i] << ' ';
	}

	return 0;
}