#include      <iostream>
#include      <fstream>
#include      <algorithm>
#include      <vector>
#include      <queue>
#include      <deque>

#define MAX  50001
#define INF (1 << 30)

using namespace std;

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

int n, m, d[MAX], viz[MAX], f[MAX];

vector < pair <int, int> > G[MAX];
deque < int > q;


int main() {
   
	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> n >> m;

	for (int i = 1; i <= m; i++) {
		int x, y, c;
		in >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}

	for (int i = 2; i <= n; i++) d[i] = INF;
	q.push_back(1);
	while (!q.empty()) {
		int nod_curent = q.front();
		viz[nod_curent] = 0;

		for (int i = 0; i < G[nod_curent].size(); i++) {
			int vecin = G[nod_curent][i].first;
			int cost = G[nod_curent][i].second;

			if (d[vecin] > d[nod_curent] + cost) {
				d[vecin] = d[nod_curent] + cost;

				if (!viz[vecin]) {
					viz[vecin] = 1;
					f[vecin]++;
					q.push_back(vecin);
					if (f[vecin] == n) {
						out << "Ciclu negatic!";
						return 0;
					}
				}
			}
		}

		q.pop_front();

	}

	for (int i = 2; i <= n; i++) out << d[i] << ' ';

    return 0;

}