#include <bits/stdc++.h>

using namespace std;

#define NMAX 50005
const int INF = 1e9;

int n, m;
int dist[NMAX];
vector<pair<int, int>> adj[NMAX];
queue<int> q;
int cnt[NMAX];
bool in_queue[NMAX];

bool bellmanford(int src)
{
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[src] = 0;
	in_queue[src] = true;
	q.push(src);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		in_queue[v] = false;
		for (auto l : adj[v]) {
			int d = l.first;
			int c = l.second;
			if (dist[v] + c < dist[d]) {
				dist[d] = dist[v] + c;
				if (!in_queue[d]) {
					q.push(d);
					in_queue[d] = true;
					cnt[d]++;
					if (cnt[d] > n) {
						return false;
					}
				}
			}
		}
	}
	return true;
}

int main()
{
	/*freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);*/
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		adj[x].push_back({y, c});
	}
	bool ok = bellmanford(1);
	if (!ok) {
		fout << "Ciclu negativ!\n";
		return 0;
	}
	for (int i = 2; i <= n; i++)
		fout << dist[i] << ' ';
	fout << '\n';
	return 0;
}