#include <fstream>
#include <vector>
#include <deque>
#include <queue>
#include <iostream>
#include <set>

using namespace std;

const int inf = 1e9;
const int NMAX = 5e4 + 10;
vector < pair < int, int > > v[NMAX];
int dist[NMAX], was[NMAX];

int dist2[NMAX];
bool viz[NMAX];

int main() {	
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	int n, m;
	f >> n >> m;
	while (m--) {
		int x, y, z;
		f >> x >> y >> z;
		v[x].push_back({ y,z });
	}

	for (int i = 1; i <= n; i++) {
		v[0].push_back({ i, 0 });
		dist[i] = inf;
	}

	deque < int > q;
	q.push_back(0);
	while (!q.empty()) {
		int node = q.front();
		q.pop_front();

		for(auto it : v[node])
			if (dist[it.first] > dist[node] + it.second) {
				dist[it.first] = dist[node] + it.second;
				q.push_back(it.first);
				was[it.first]++;
				if (was[it.first] == n) {
					cout << "Ciclu negativ!";
					return 0;
				}
			}
	}

	for (int i = 1; i <= n; i++) 
		for (auto& it : v[i]) {
			it.second += dist[i] - dist[it.first];
		}

	for (int i = 2; i <= n; i++)
		dist2[i] = inf;
	priority_queue < pair < int, int > > d;
	d.push({ 0, 1 });
	while (!d.empty()) {
		int node = d.top().second;
		d.pop();

		if (viz[node])
			continue;
		viz[node] = 1;

		for (auto it : v[node])
			if (dist2[it.first] > dist2[node] + it.second) {
				dist2[it.first] = dist2[node] + it.second;
				d.push({ -dist2[it.first], it.first });
			}
	}

	for (int i = 2; i <= n; i++)
		g << dist2[i] - dist[1] + dist[i] << " ";
	

	return 0;
}