#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

const int mxN = 5e4 + 5, inf = 2e9;
int n, m, d[mxN];
vector<pair<int, int>> adj[mxN];
set<int> nodes;

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

void bellmanFord(int st) {

	for (int i = 1; i <= n; i++) {
		d[i] = inf;
	}
	d[st] = 0;

	nodes.insert(st);
	for (int k = 1; k <= n; k++) {
		bool changed = false;

		set<int> s;
		for (auto u : nodes) {
			for (auto p : adj[u]) {
				int v = p.second;
				int w = p.first;
				if (d[u] + w < d[v]) {
					d[v] = d[u] + w;
					changed = true;
					s.insert(v);
				}
			}
		}

		nodes = s;

		if (!changed) {
			break;
		}

		if (k == n && changed) {
			fout << "Ciclu negativ!\n";
			exit(0);
		}
	}
}

int main() {

	readInput();
	bellmanFord(1);
	for (int i = 2; i <= n; i++) {
		fout << d[i] << " ";
	}
	return 0;
}