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

int N,M,C[maxn],B[maxn];
queue<int> Q;
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].push_back({y,c});
	}
	for(int i = 2;i<=N;i++) C[i]=(1<<30);
	Q.push(1);
	while(!Q.empty()){
		int x = Q.front(); Q.pop();
		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.push(y.cl);
	}
	for(int i = 2;i<=N;i++) cout << C[i] << ' ';
}