#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

#define MAX 50005
#define INF 9999999

using namespace std;

typedef struct {
	int d, c;
} Edge;

vector < vector <Edge> > G;
int N, M;
int dist[MAX];
bool inQ[MAX];

void read () {
	scanf ("%d %d", &N, &M);
	
	G.resize(N+1);
	for (int i = 0; i < M; ++i) {
		int x;
		Edge e;
		scanf("%d %d %d", &x, &e.d, &e.c);
		
		G[x].push_back(e);
	}
}

void bellmanFord () {
	memset(dist, INF, sizeof(dist));
	
	queue <int> Q;
	Q.push(1);
	inQ[1] = true;
	dist[1] = 0;
	int count = 0;
	while (!Q.empty()) {
		int x = Q.front();
		inQ[x] = false;
		Q.pop();
		vector <Edge>::iterator it;
		for (it = G[x].begin(); it != G[x].end(); ++it) {
			if (dist[it->d] > dist[x] + it->c) {
				dist[it->d] = dist[x] + it->c;
				if (!inQ[it->d]) {
					Q.push(it->d);
					inQ[it->d] = true;
					++count;
					if (count == N) {
						printf("Ciclu negativ!");
						return;
					}
				}
			}
		}
	}
	
	for (int i = 2; i <= N; ++i) {
		printf("%d ", dist[i]);
	}
}
int main (void) {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	
	read();
	bellmanFord();
	
	return 0;
}