#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50003;

int n,m;
bool negative_cycle = 0;
int pas[NMAX];
int dist[NMAX];

struct muchie{
	int y,c;
};
vector<vector<muchie> >v(NMAX);

// Complexitate O(N * M) muchii * noduri
void bellmanford() {
	queue<int> q;
	q.push(1);
	for(int i = 1; i <= n; i++)
		dist[i] = INT_MAX;
	dist[1] = 0;
	pas[1] = 1;
	while(!q.empty() && !negative_cycle) {
		int nod = q.front();
		q.pop();
		for(muchie m:v[nod]) {
			int y = m.y;
			int cost = m.c;
			if(dist[y] > dist[nod] + cost) {
				pas[y]++;
				if(pas[y] == n) {
					negative_cycle = 1;
				}
				dist[y] = dist[nod] + cost;
				q.push(y);
			}
		}
		
	}
}

int main() {
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i++) {
		int x,y,c;
		scanf("%d %d %d",&x,&y,&c);
		v[x].push_back({y,c});
	}
	bellmanford();
	if(negative_cycle) {
		puts("Ciclu negativ!");
		return 0;
	}
	for(int i = 2; i <= n; i++)
		printf("%d ",dist[i]);
	printf("\n");
	return 0;
}