#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <limits>

using namespace std;

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

const int oo = 2147483647;
const size_t dim = 50001;
int n, m; //noduri, muchii
int d[dim]; //distantele
int viz[dim];
struct cmp {
	bool operator()(int i, int j) {
		return d[i] > d[j];
	}
};

vector<pair<int, int >>G[dim]; //graful
queue<int>q;


void citire() {
	in >> n >> m;
	for (int i = 0; i < m; i++) {
		int nP, nF, cost;
		in >> nP >> nF >> cost;
		G[nP].push_back(make_pair(nF, cost));
	}
}

int bf(int nod) {

	for (int i = 1; i <= n; i++) {
		d[i] = oo;
	}
	d[nod] = 0;
	q.push(nod);
	viz[nod]++;

	while (q.empty() == false) {
		int x = q.front();
		q.pop();
		for (auto& k : G[x]) {
			int vecin = k.first;
			int cost = k.second;
			if (d[vecin] > d[x] + cost) {
				if (viz[vecin] == n - 1) {
					out << "Ciclu negativ!\n";
					return -1;
				}
				d[vecin] = d[x] + cost;
				viz[vecin]++;
				q.push(vecin);
			}
		}
	}
	return 0;
}

int main() {

	citire();
	if (bf(1) != -1) {
		for (int i = 2; i <= n; i++) {
			out << d[i] << " ";
		}
	}

	return 0;
}