#include <bits/stdc++.h>
#define maxm 250100
#define maxn 50100
#define pb push_back
#define pii pair<int,int>
#define cl first
#define pr second
using namespace std;

int N,M,q,C[maxn],B[maxn],Q[maxm];
vector<pii> V[maxn];
int main(){
	ifstream cin("bellmanford.in");
	ofstream cout("bellmanford.out");
    cin >> N >> M;
    for(int x,y,c;M--;){
		cin >> x >> y >> c;
		V[x].pb({y,c});
	}
	for(int i = 2;i<=N;i++) C[i]=(1<<30);
	Q[++q] = 1;
	while(q){
		int x = Q[q--];
		B[x]++;
		if(B[x] == N) return cout << "Ciclu negativ!",0;
		for(auto y:V[x]) if(C[y.cl] > C[x] + y.pr) C[y.cl] = C[x] + y.pr, Q[++q] = y.cl;
	}
	for(int i = 2;i<=N;i++) cout << C[i] << ' ';
}