#include <algorithm>
#include <ctime>
#include <vector>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <cmath>
#include <unordered_map>
#include <iomanip>
#include <queue>
#include <tuple>

using namespace std;


int dist[50001];
bool inQueue[50001];
int countInQueue[50001];
vector<pair<int, int>> graf[50001];

int main() {
	ifstream cin("bellmanford.in");
	ofstream cout("bellmanford.out");

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) dist[i] = 1e9;

	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		graf[a].emplace_back(b, w);
	}

	queue<int> q;
	dist[1] = 0;
	q.push(1);
	inQueue[1] = true;
	countInQueue[1] = 1;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		inQueue[u] = false;

		for (auto [v, w] : graf[u]) {
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				if (!inQueue[v]) {
					q.push(v);
					inQueue[v] = true;
					countInQueue[v]++;

					if (countInQueue[v] > n) {
						cout << "Ciclu negativ!";
						return 0;
					}
				}
			}
		}
	}

	for (int i = 2; i <= n; i++) {
		if (dist[i] == 1e9) cout << "1e9 ";
		else cout << dist[i] << " ";
	}

	return 0;
}