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

int n, m;
int viz[50001];
vector<pair<int, int>> a[50001];
int d[50001];
bool ciclu = 0;
const int Inf = 1e9 + 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;

void bmf(int x) {
	int i;
	pair<int, int> p, cur;
	viz[x] = 1;
	d[x] = 0;
	Q.push({0, 1});
	while (!Q.empty()) {
		p = Q.top();
		Q.pop();
		viz[p.second]++;

		if (viz[p.second] >= n) {
			ciclu = 1;
			break;
		}

		for (i = 0; i < a[p.second].size(); i++) {
			cur = a[p.second][i];
			if (d[cur.second] > d[p.second] + cur.first) {
				d[cur.second] = d[p.second] + cur.first;
				Q.push({d[cur.second], cur.second});
			}
		}

	}
}

void read() {
	int i, cost, x, y;
	ifstream f("bellmanford.in");
	f >> n >> m;
	for (i = 1; i <= m; i++) {
		f >> x >> y >> cost;
		a[x].emplace_back(cost, y);
	} 
	f.close();
}

void output() {
	ofstream g("bellmanford.out");
	if (ciclu == 1)
		g << "Ciclu negativ!";
	else {
		int i;
		for (i = 2; i <= n; i++)
			g << d[i] << ' ';
	}
	g.close();
}

int main() {
	read();
	int i;
	for (i = 2; i <= n; i++)
		d[i] = Inf;
	bmf(1);
	output();
	return 0;
}