#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=50001;
using namespace std;

int n,m,sw=1,dist[maxn],cnt[maxn];

vector<vector<pair<int,int>>> A(maxn, vector<pair<int,int>>());

int main(){
	ifstream cin("bellmanford.in");
	ofsteam cout("bellmanford.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int c1,c2,c3;
		cin>>c1>>c2>>c3;
		A[c1-1].push_back({c2-1,c3});
	}
	for(int i=1;i<n;i++)dist[i]=1e9;
	queue<int> Q;
	bitset<maxn> B(0);
	Q.push(0);
	B[0]=1;
	while(!Q.empty()&&sw){
		int i=Q.front();
		Q.pop();
		B[i]=0;
		for(int j=0;j<A[i].size();j++){
			if(dist[A[i][j].F]>dist[i]+A[i][j].S){
				dist[A[i][j].F]=dist[i]+A[i][j].S;
				if(!B[A[i][j].F]){
					if(cnt[A[i][j].F]>n){
						sw=0;
					}
					else{
						Q.push(A[i][j].F);
						cnt[A[i][j].F]++;
						B[A[i][j].F]=1;
					}
				}
			}
		}
	}
	if(!sw){
		cout<<"Ciclu negativ!"<<endl;
	}
	else{
		for(int i=1;i<n;i++)cout<<dist[i]<<" ";
	}
}