#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector<pair<int, int>  > v[50005];
int N, M;
int dist[50005];
bool visited[50005];
int countNodes[50005];

void read() {

	int x, y, z;

	f >> N >> M;
	for (int i = 0; i < M; ++i) {
		f >> x >> y >> z;
		v[x].push_back(make_pair(y, z));
	}
}

bool bellmanFord() {

	int node;
	bool negativeCycle = false;
	queue<int> q;

	dist[1] = 0;
	visited[1] = true;
	q.push(1);

	for (; q.size() && negativeCycle == false;) {
		node = q.front();
		q.pop();
		visited[node] = false;

		for (auto &x : v[node]) {
			if (dist[node] < 2147000000) {
				if (dist[x.first] > dist[node] + x.second) {
					dist[x.first] = dist[node] + x.second;
					if (visited[x.first] == false) {
						if (countNodes[x.first] > N) {
							negativeCycle = true;
						}
						else {
							q.push(x.first);
							visited[x.first] = true;
							countNodes[x.first] ++;
						}
					}
				}
			}
		}
	}

	return negativeCycle;
}

int main()
{
	read();
	for (int i = 1; i <= N; ++i) {
		dist[i] = 2147000000;
	}
	bool ok = bellmanFord();
	if (ok == false) {
		for (int i = 2; i <= N; ++i) {
			g << dist[i] << " ";
		}
	}
	else {
		g << "Ciclu negativ!\n";
	}
    return 0;
}