#include <fstream>
#include <vector>
#include <queue>
#define DIM 50001
#define INF 250000001
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, x, y, c, d[DIM], f[DIM];
bool viz[DIM];
vector<pair<int, int>> l[DIM];
queue<int> q;
int main() {
	fin >> n >> m;
	while (m--) {
		fin >> x >> y >> c;
		l[x].push_back({y, c});
	}
	for (int i = 2; i <= n; i++)
		d[i] = INF;
	d[1] = 0;
	viz[1] = true;
	f[1] = 1;
	q.push(1);
	while (!q.empty()) {
		int nod = q.front();
		q.pop();
		viz[nod] = false;
		for (int i = 0; i < l[nod].size(); i++) {
			int vec = l[nod][i].first;
			int cost = l[nod][i].second;
			if (d[nod] + cost < d[vec]) {
				d[vec] = d[nod] + cost;
				if (viz[vec] == 0) {
					f[vec]++;
					if (f[vec] == n) {
						fout << "Ciclu negativ!";
						return 0;
					}
					viz[vec] = true;
					q.push(vec);
				}
			}
		}
	}
	for (int i = 2; i <= n; i++)
		fout << d[i] << " ";
	return 0;
}