#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <queue>

using std::vector;
using std::queue;

const int oo = INT_MAX / 2;

void citire(int& n,int& m, vector<vector<std::pair<int,int>>>& g) {
	std::ifstream cin("bellmanford.in");
	cin >> n >> m;
	g.resize(n + 1);
	int x, y, w;
	for (int i = 0;i < m;i++) {
		cin >> x >> y>>w;
		g[x].push_back({ y,w });
	}
	cin.close();
}

bool bellmanFord(const int& sursa,const int& n, vector<vector<std::pair<int, int>>>& g, 
	queue<int>& q,vector<bool>& inCoada, vector<int>& count,vector<int>& d) {
	d.resize(n + 1, oo);
	count.resize(n + 1, 0);
	inCoada.resize(n+1,false);
	d[sursa] = 0;
	q.push(sursa);
	inCoada[sursa] = true;
	while (!q.empty()) {
		int nod = q.front();
		q.pop();
		inCoada[nod] = false;
		for (unsigned i = 0;i < g[nod].size();i++) {
			int vecin = g[nod][i].first;
			int cost = g[nod][i].second;
			if (d[vecin] > d[nod] + cost) {
				d[vecin] = d[nod] + cost;
				if (!inCoada[vecin]) {
					q.push(vecin);
					inCoada[vecin] = true;
					count[vecin]++;
					if (count[vecin] > n) {
						return false;
					}
				}
			}
		}
	}
	return true;

}
void afisare(const int& n, const vector<int>& d,bool& ok) {
	std::ofstream cout("bellmanford.out");
	if (!ok) {
		cout << "Ciclu negativ!";
	}
	else {
		for (int i = 2;i <= n;i++) {
			cout << d[i] << ' ';
		}
	}
	cout.close();
}
int main() {
	int n, m;
	vector<vector<std::pair<int,int>>> g;
	queue<int> q;
	vector<int> d;
	vector<bool> inCoada;
	vector<int> count;
	citire(n, m, g);
	bool ok = bellmanFord(1, n, g, q, inCoada, count, d);
	afisare(n, d, ok);
	return 0;
}