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

using namespace std;

struct Nod {
	int key, cost;
};

vector <Nod> L[50001], st;
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;
	
	st.push_back((Nod){1, 0});
	while(st.size() > 0 && count--) {
		i = st[st.size() - 1].key;
		st.pop_back();
		
		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;
				st.push_back((Nod){x, dmin[x]});
			}
		}
	}
	
	// verific daca exista un ciclu negativ
	
	if(st.size() > 0) printf("Ciclu negativ!\n");
	else for(i = 2; i <= n; i++) printf("%d ", dmin[i]);
	
	return 0;
}