#include <fstream>
#include <bitset>
#include <queue>
#include <vector>

#define oo 1 << 30
#define NMax 50001

using namespace std;

int N, M, x, y, c;
bool negativeCycle = false;
vector <pair <int, int>> G[NMax];
vector <int> dist(NMax, oo), countInQ(NMax, 0);
queue <int> Q;
bitset <NMax> inQ(false);

int main()
{
	int i;

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

	fin >> N >> M;

	for (i = 1; i <= M; i++) {
		fin >> x >> y >> c;

		G[x].push_back({ y, c });
	}

	dist[1] = 0, Q.push(1), inQ[1].flip();

	while (!Q.empty() && !negativeCycle) {
		int currentNode = Q.front();
		Q.pop();
		inQ[currentNode] = false;

		for (auto node : G[currentNode]) {
			if (dist[currentNode] < oo) {
				if (dist[node.first] > dist[currentNode] + node.second) {
					dist[node.first] = dist[currentNode] + node.second;

					if (!inQ[node.first]) {
						if (countInQ[node.first] > N) {
							negativeCycle = true;
						}
						else {
							Q.push(node.first);
							inQ[node.first] = true;
							countInQ[node.first]++;
						}
					}
				}
			}
		}
	}

	if (negativeCycle) {
		fout << "Ciclu negativ\n";
	}
	else {
		for (i = 2; i <= N; i++) {
			fout << dist[i] << " ";
		}
	}

	fin.close();
	fout.close();
}