#include <iostream>
#include <vector>
#include <fstream>
using std::vector;
#define MMax 250000
#define NMax 50000
const int oo = INT_MAX / 2;
struct edge {
	int u, v, w;
	int d;
};
void citire(int& n, int& m, vector<edge>& e) {
	std::ifstream cin("bellmanford.in");
	e.resize(MMax+1);
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	cin.close();
}
void initializare(vector<int>& d,const int& n) {
	d.resize(NMax);
	for (int i = 1;i <= n;i++) {
		d[i] = oo;
	}
	d[1] = 0;
}
bool bellmanFord(const int& s,const int& n, const int& m, vector<edge>& e,vector<int>& d) {
	initializare(d,n);
	for (int i = 1;i < n - 1;i++) {
		for (const auto& ed : e) {
			if (d[ed.v] > d[ed.u] + ed.w) {
				d[ed.v] = d[ed.u] + ed.w;
			}
		}
	}
	for (const auto& ed : e) {
		if (d[ed.v] > d[ed.u] + ed.w)
			return false;
	}
	return true;
}
int main() {
	vector<edge> edges;
	int n, m;
	citire(n, m, edges);
	vector<int> d;
	bool ok=bellmanFord(1,n, m, edges,d);
	std::ofstream cout("bellmanford.out");
	if (!ok) {
		cout << "Ciclu negativ!";
	}
	else {
		for (int i = 2;i <= n;i++) {
			cout << d[i]<<' ';
		}
	}
	cout.close();
}