#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50003;

int n,m;
bool negative_cycle = 0;
int pas[NMAX];
int dist[NMAX];
bitset<NMAX> in_queue;

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;
	while(!q.empty() && !negative_cycle) {
		int nod = q.front();
		q.pop();
		in_queue[nod] = 0;
		for(muchie m:v[nod]) {
			int y = m.y;
			int cost = m.c;
			if(dist[y] > dist[nod] + cost) {
				dist[y] = dist[nod] + cost;
				if(!in_queue[y]) {
					if(pas[y] > n) {
						negative_cycle = 1;
					}
					pas[y]++;
					q.push(y);
					in_queue[y] = 1;					
				}

			}
		}
	}
}

int main() {
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= m; 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]);
	return 0;
}