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

using namespace std;

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

const int infinity = 1000000;
const size_t dim = 50001;
int nodes, m; //noduri, muchii
int d[dim]; //distantele
int check[dim];
vector<pair<int, int >>graph[dim]; //graful
queue<int>q;

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

int bf(int nod) {

	for (int i = 1; i <= nodes; i++) {
		d[i] = infinity;
	}
	d[nod] = 0;
	q.push(nod);
	check[nod]++;

	while (q.empty() == false) {
		int u = q.front();
		q.pop();
		/*
		for (auto& k : G[u]) {
			int vecin = k.first;
			int cost = k.second;
			if (d[vecin] > d[u] + cost) {
				if (check[vecin] == n - 1) {
					out << "Ciclu negativ!\n";
					return 1;
				}
				d[vecin] = d[u] + cost;
				check[vecin]++;
				q.push(vecin);
			}
		}
		*/
		for (size_t j = 0; j < graph[u].size(); j++) {
			int vecin = graph[u][j].first;
			int cost = graph[u][j].second;
			if (d[vecin] > d[u] + cost) {
				if (check[vecin] == nodes - 1) {
					out << "Ciclu negativ!\n";
					return -1;
				}
				d[vecin] = d[u] + cost;
				q.push(vecin);
				check[vecin]++;
			}
		}
	}
	return 0;
}

int main() {

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

	return 0;
}