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

#define PR std::pair<int, int>
#define INF 0x3f3f3f3f

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

std::vector<std::vector<PR> > G;
std::vector<int> viz, iq, D;
std::queue<int> Q;
int N, M, has_negative_cycle = 0;

void read() {
	fin >> N >> M;

	int x, y, c;
	G.resize(N + 1);
	viz = std::vector<int>(N + 1, 0);
	iq = std::vector<int>(N + 1, 0);
	D = std::vector<int>(N + 1, INF);

	while (M--) {
		fin >> x >> y >> c;
		G[x].push_back({ y, c });
	}
}

void BellmanFord(int start) {
	viz[start] = iq[start] = 1;
	Q.push(start);
	D[start] = 0;

	while (!Q.empty()) {
		int curr_node = Q.front();
		Q.pop();
		viz[curr_node] = 0;

		for (auto elem : G[curr_node]) {
			int vecin = elem.first, cost = elem.second;

			if (D[vecin] > D[curr_node] + cost) {
				D[vecin] = D[curr_node] + cost;

				if (!viz[vecin]) {
					iq[vecin]++;

					if (iq[vecin] > N) {
						has_negative_cycle = 1;
						return;
					}

					Q.push(vecin);
					viz[vecin] = 1;
				}
			}
		}
	}
}

int main() {
	read();
	BellmanFord(1);
	if (has_negative_cycle)
		fout << "Ciclu negativ!";
	else
		for (int i = 2; i <= N; ++i)
			fout << D[i] << ' ';
}