#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];

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() {

	dist[1] = 0;
	for (int i = 1; i <= N - 1; ++i) {
		for (int j = 1; j <= M; ++j) {
			for (auto &x : v[j]) {
				if (dist[x.first] > dist[j] + x.second) {
					dist[x.first] = dist[j] + x.second;
				}
			}
		}
	}

	for (int j = 1; j <= M; ++j) {
		for (auto &x : v[j]) {
			if (dist[x.first] > dist[j] + x.second) {
				g << "Ciclu negativ!\n";
				return 0;
			}
		}
	}
	return 1;
}

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