/*
Bellman-Ford.
*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define MAXN	50001

using namespace std;

int nr_noduri, nr_muchii;
vector< pair <int, int> > graf[MAXN];
queue<int> coada;
int drum[MAXN], nr_elem_coada[MAXN];
bool marcat[MAXN];

int drum_min () {
	int v;
	
	memset(marcat, 0, sizeof(marcat));
	memset(nr_elem_coada, 0, sizeof(nr_elem_coada));
	memset(drum, INT_MAX, sizeof(drum));

	drum[1] = 0;
	coada.push(1);
	marcat[1] = true;

	while (!coada.empty()) {
		int u = coada.front();
		coada.pop();
		marcat[u] = false;

		for (v = 0; v < graf[u].size(); v++) {
			if (drum[graf[u][v].first] == INT_MAX || drum[u] + graf[u][v].second < drum[graf[u][v].first]) {
				drum[graf[u][v].first] = drum[u] + graf[u][v].second;
				if (!marcat[graf[u][v].first]) {
					coada.push(graf[u][v].first);
					marcat[graf[u][v].first] = true;
					nr_elem_coada[graf[u][v].first]++;
				}
				if (nr_elem_coada[graf[u][v].first] >= nr_noduri)
					return 1;
			}
		}
	}
	return 0;
}

int main () {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	int i, x, y, z;
	scanf("%d %d", &nr_noduri, &nr_muchii);
	for (i = 0; i < nr_muchii; i++) {
		scanf("%d %d %d", &x, &y, &z);
		graf[x].push_back(make_pair(y, z));
	}

	int e_ciclu_neg = drum_min();

	if (!e_ciclu_neg)
		for (i = 2; i <= nr_noduri; i++)
			printf("%d ", drum[i]);
	else
		printf("Ciclu negativ!\n");

	return 0;
}