#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int kMaxN = 50005;
const int kInf = 0x3f3f3f3f;

int N, M, dist[kMaxN];
vector<pair<int, int>> G[kMaxN];

queue<int> q;
bool in_q[kMaxN];
int q_cnt[kMaxN];
bool negative_cycle;

void Read() {
	ifstream fin("bellmanford.in");
	fin >> N >> M;
	while (M--) {
		int x, y, c;
		fin >> x >> y >> c;
		G[x].emplace_back(y, c);
	}
}

void Relax(int node, int cost) {
	if (cost < dist[node]) {
		dist[node] = cost;
		if (!in_q[node]) {
			q.push(node);
			in_q[node] = true;
			++q_cnt[node];
			if (q_cnt[node] == N)
				negative_cycle = true;
		}
	}
}

void Solve() {
	memset(dist, kInf, sizeof dist);
	dist[1] = 0;
	q.push(1);
	in_q[1] = true;
	q_cnt[1] = N - 1;
	while (!q.empty() && !negative_cycle) {
		int node = q.front();
		q.pop();
		in_q[node] = false;
		for (auto it : G[node])
			Relax(it.first, dist[node] + it.second);
	}
}

void Print() {
	ofstream fout("bellmanford.out");
	if (negative_cycle)
		fout << "Ciclu negativ!";
	else
		for (int i = 2; i <= N; ++i)
			fout << dist[i] << " ";
	fout << "\n";
}

int main() {
	Read();
	Solve();
	Print();
	return 0;
}