#include<fstream>
#include<vector>
#include<queue>
#define pb push_back
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int NMAX = 50005;
const int MMAX = 250005;
const int INF = 1 << 30;
int N,M;
struct vertex{
	int node,cost;
};
vector<vertex> G[NMAX];
queue<int> q;
int inside[NMAX];
int inside_cnt[NMAX];
int neg_cycle=false;
int D[NMAX];
int main(){
	in>>N>>M;
	for(int i=1;i<=M;i++){
		int a,b,c;
		in>>a>>b>>c;
		vertex u;
		u.node=b;
		u.cost=c;
		G[a].pb(u);
	}
	D[1]=0; for(int i=2;i<=N;i++) D[i]=INF;
	q.push(1);
	inside[1]=true;
	while(!q.empty() && !neg_cycle){
		int x=q.front(); q.pop();
		inside[x]=false;
		for(vector<vertex>::iterator it=G[x].begin();it!=G[x].end();++it){
			if( D[it->node] > D[x] + it->cost ){
				D[it->node] = D[x] + it->cost;
				if(!inside[it->node]){
					if(inside_cnt[it->node] > N){
						neg_cycle=true;
					}
					else{
						q.push(it->node);
						inside[it->node]=true;
						inside_cnt[it->node]++;
					}
				}
			}
		}
	}
	if(neg_cycle) out<<"Ciclu negativ!"<<'\n';
	else{
		for(int i=2;i<=N;i++) out<<(D[i]==INF?0:D[i])<<' ';
		out<<'\n';
	}
	return 0;
}