#include <iostream>
#include <fstream>

#define INF 0x3f3f3f3f
#define MAXN 50005

int N, M;
std::vector<std::pair<int, int> > listN[MAXN];
int que[2][MAXN];
int d[MAXN], h[MAXN];

int bellmanFord()
{
	int fst = 0, lst = 1;
	que[fst][0] = 1;
	que[fst][1] = 1;
	
	memset (d, INF, sizeof(d));
	memset (h, 0, sizeof(h));
	d[1] = 0;
	
	for (int step = 1; step <= N+1; ++ step, fst ^= 1, lst ^= 1) {
		que[lst][0] = 0;
		for (int k = 1; k <= que[fst][0]; ++ k) {
			int node = que[fst][k];
			for (auto p : listN[node]) {
				if (d[p.first] > d[node] + p.second) {
					d[p.first] = d[node] + p.second;
					if (h[p.first] != step) {
						que[lst][0]++;
						que[lst][que[lst][0]] = p.first;
						h[p.first] = step;
					}
				}
			}
		}
	}
	
	if (que[fst][0]) {
		// has negative cycle
		return 1;
	}
	
	return 0;
}

int main ()
{
	std::ifstream in("bellmanford.in");
	
	in >> N >> M;
		
	for (int i = 0; i < M; ++ i) {
		int x,y,c;
		in >> x >> y >> c;
		listN[x].push_back(std::make_pair(y, c));
	}
	
	in.close();
	
	int negCycle = bellmanFord();
	
	std::ofstream out("bellmanford.out");
	
	if (negCycle) {
		out << "Ciclu negativ!\n";
	} else {
		for (int i = 2; i < N; ++ i) {
			out << d[i] << " ";
		}
		out << d[N] << "\n";
	}
	
	out.close();
	
	return 0;
}