#include <bits/stdc++.h>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int INF = 1e12;
const int MAXN = 50003;

vector<vector<pair<int, int>>> g(MAXN);

int main() {

	int n, m;
	in >> n >> m;
	
	for(int i = 1; i <= m; i++) {
		int x, y, cost;
		in >> x >> y >> cost;
		g[x].push_back({y, cost});
	}	

	// SPFA - Shortest Path Faster Algorithm

	queue<int> q;
	vector<long long> dist(n + 1, INF), seen(n + 1, 0);
	vector<bool> in_queue(n + 1, false);

	dist[1] = 0;
	q.push(1);
	while(!q.empty()) {
		int node = q.front();
		q.pop();
		in_queue[node] = false;
		for(auto [son, cost] : g[node]) {
			if(dist[node] + cost < dist[son]) {
				dist[son] = dist[node] + cost;
				if(!in_queue[son]) {
					q.push(son);
					in_queue[son] = true;
					seen[son]++;
					if(seen[son] > n) {
						cout << "Ciclu negativ!\n";
						return 0;
					}
				}
			}
		}
	}

	for(int i = 2; i <= n; i++) {
		out << dist[i] << ' ';
	}

	return 0;
}