#include <fstream>
#include <vector>
#include <deque>

using namespace std;

const int inf = 1e9;
const int NMAX = 5e4 + 10;
vector < pair <int, int> > v[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 });
	}

	vector < int > dist(n + 5, inf);
	vector < int > was(n + 5, 0);
	deque < int > q;
	q.push_back(1);
	dist[1] = 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) {
					g << "Ciclu negativ!";
					return 0;
				}
			}
		}
	}
	
	for (int i = 2; i <= n; i++)
		g << dist[i] << " ";

	return 0;
}