#include<cstdio>
#include<vector>
#include<queue>
#define inf (1<<30)

using namespace std;

struct Nod {
	int key, cost;
};

vector <Nod> L[50001];
queue <Nod> q;
int dmin[50001];
int n, m;

int main() {
	int i, j, x, y, c, count;
	
	freopen("bellmanford.in", "r", stdin), freopen("bellmanford.out", "w", stdout);
	scanf("%d %d", &n, &m);
	
	for(i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &c);
		L[x].push_back((Nod){y, c});
	}
	
	dmin[1] = 0, count = n * (n - 1);
	for(i = 2; i <= n; i++) dmin[i] = inf;
	
	q.push((Nod){1, 0});
	while(!q.empty() && count--) {
		i = q.front().key;
		q.pop();
		
		for(j = 0; j < (int)L[i].size(); j++) {
			x = L[i][j].key;
			c = L[i][j].cost;
			if(dmin[x] > dmin[i] + c) {
				dmin[x] = dmin[i] + c;
				q.push((Nod){x, dmin[x]});
			}
		}
	}
	
	// verific daca exista un ciclu negativ
	
	if(!q.empty()) printf("Ciclu negativ!\n");
	else for(i = 2; i <= n; i++) printf("%d ", dmin[i]);
	
	return 0;
}