#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
#include <set>
#include <string>
#include <map>
#include <stdlib.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct vect {
	int nod, cost;
	bool operator<(const vect& other) const {
		return (*this).cost > other.cost;
	}
};
int n, m;
vector <vect> v[50005];
int dist[50005];
priority_queue<vect> q;
void bellman_ford(int nod) {
	for (int i = 1; i <= n; i++) dist[i] = 1e9;
	dist[nod] = 0;
	q.push({ nod, 0 });
	long long pas = 0;
	while (!q.empty() && pas <= 1LL * n * m) {
		pas++;
		vect cr = q.top();
		q.pop();
		if (cr.cost != dist[cr.nod]) continue;
		for (auto el : v[cr.nod]) {
			if (el.cost + cr.cost < dist[el.nod]) {
				dist[el.nod] = el.cost + cr.cost;
				q.push({ el.nod, el.cost + cr.cost });
			}
		}
	}
}
int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		v[x].push_back({ y,c });
	}
	bellman_ford(1);
	for (int i = 1; i <= n; i++) {
		for (auto el : v[i]) {
			if (dist[i] + el.cost < dist[el.nod]) {
				fout << "Ciclu negativ!";
				exit(0);
			}
		}
	}
	for (int i = 2; i <= n; i++)
		fout << dist[i] << " ";
}