#include <iostream>
#include <vector>
#include <functional>
#include <limits.h>
#include <queue>
#define MAX_N 50005
#define MAX_E 250005

using namespace std;

vector<tuple<int, int, int> > v[MAX_N];
int dp[MAX_N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
int used[MAX_E];

int main()
{
	FILE *fin = fopen("bellmanford.in", "r");
	FILE *fout = fopen("bellmanford.out", "w");
	int n, m;
	fscanf(fin, "%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		fscanf(fin, "%d %d %d", &a, &b, &c);
		a--; b--;
		v[a].push_back({b, c, i});
	}
	for (int i = 0; i < n; i++)
		dp[i] = INT_MAX;
	dp[0] = 0;
	pq.push({0, 0});
	
	while (!pq.empty()) {
		auto tp = pq.top();
		pq.pop();
		int i = tp.second;
		for (auto edge: v[i]) {
			int j = get<0>(edge);
			int c = get<1>(edge);
			int index = get<2>(edge);
			if (dp[i] == INT_MAX)
				continue;
			if (dp[j] > dp[i] + c) {
				dp[j] = dp[i] + c;
				used[index]++;
				if (used[index] > n) {
					fprintf(fout, "Ciclu negativ!\n");
					return 0;
				}
				pq.push({dp[j], j});
			}
		}
	}

	for (int i = 1; i < n; i++)
		fprintf(fout, "%d ", dp[i]);
	fprintf(fout, "\n");

}