#include<cstdio>
#include<vector>
#define inf 1005

using namespace std;

struct Nod {
	int key, cost;
};

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

int main() {
	int i, j, x, y, c;
	
	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;
	for(i = 2; i <= n; i++) dmin[i] = inf;
	
	for(i = 1; i <= n; i++) {
		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;
				i = i > x ? x : i; // !important
			}
		}		
	}
	
	// verifiic daca exista un ciclu negativ
	for(i = 1; i <= n; i++) {
		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) {
				printf("Ciclu negativ!\n");
				return 0;
			}
		}		
	}
	
	for(i = 2; i <= n; i++) printf("%d ", dmin[i]);
	
	return 0;
}