#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <functional>
#include <set>
#define NMAX 50005
#define endl '\n';

using namespace std;

typedef pair<int, int> pii;

const int INF = 1e9;
const string FL = "bellmanford";
ifstream fin(FL + ".in");
ofstream fout(FL + ".out");

int n, m;
vector<pii> adj[NMAX];
bool circuitNegativ = false;

vector<int> BellmanFord(int source) {
	vector<int> d(n + 1, INF);
	vector<bool> inQ(n+1, false);
	vector<int> relax(n+1, 0);
	queue<int> q;
	d[source] = 0;
	q.push(source);
	inQ[source] = true;

	while (!q.empty()) {
		int u = q.front();
		inQ[u] = false;
		q.pop();
		for (auto& p : adj[u]) {
			int v = p.first;
			int cost = p.second;
			int change = 0;

			if (d[u] != INF && cost + d[u] < d[v]) {
				d[v] = cost + d[u];
				relax[v]++;
				change++;
				if (!inQ[v]) {
					q.push(v);
					inQ[v] = true;
				}
			}
			if (relax[v] >= n)
				circuitNegativ = true;
		}
	}
	return d;
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		fin >> u >> v >> w;
		adj[u].push_back({ v, w });
	}

	vector<int> dist = BellmanFord(1);
	if (circuitNegativ)
		fout << "Ciclu negativ!";
	else
		for (int i = 2; i <= n; ++i)
			fout << dist[i] << " ";
	return 0;
}