#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int NMAX = 5e4+5;
const int INF = 1e9+5;

int n, m;
int dist[NMAX], inq[NMAX], viz[NMAX];
vector<pii> g[NMAX];

void read() {
	cin >> n >> m;
	for (int i = 1, x, y, c; i <= m; i++) {
		cin >> x >> y >> c;
		g[x].push_back({y, c});
	}
}

void solve() {
	for (int i = 2; i <= n; i++)
		dist[i] = INF;
	queue<int> q;
	q.push(1);
	
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = false;
		if (++viz[u] > n) {
			cout << "Ciclu negativ!" << endl;
			return;
		}
		for (auto [v, c] : g[u]) {
			if (dist[v] > dist[u] + c) {
				dist[v] = dist[u] + c;
				if (!inq[v]) {
					inq[v] = true;
					q.push(v);
				}
			}
		}
	}

	for (int i = 2; i <= n; i++)
		cout << dist[i] << ' ';
}

signed main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#else
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
#endif
	read();
	solve();
	return 0;
}