using namespace std;
#include <fstream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define NN 50005
#define INFINIT 1000000000
 
vector<pair<int,int> > G[NN];
int n;
 
 
int main(){
	ifstream fin("bellmanford.in");
	int m;
	fin>>n>>m;
	for( ; m ; --m){
		int i,j,k;
		fin>>i>>j>>k;
		G[i].push_back(make_pair(j,k));
	}
	queue<int> Q;
	vector<int> InQ(n+1,0);
	vector<int> CQ(n+1,0); //de cate ori a intrat in coada un element
	vector<int> d(n+1, INFINIT);
	d[1]=0;	Q.push(1), InQ[1]=1;
	int ciclu_neg=0;
	while( !Q.empty() && !ciclu_neg ){
		int k=Q.front();
		Q.pop();
		InQ[k]=0;
		for(vector<pair<int,int> >::iterator I=G[k].begin(); I<G[k].end(); ++I)
			if(d[I->first] > d[k] + I->second ){
				d[I->first] = d[k] + I->second;
				if(!InQ[I->first])
					if(CQ[I->first]>n)
						ciclu_neg=1;
					else{
						Q.push(I->first);
						InQ[I->first]=1;
						++CQ[I->first];
				}
			}
	}
	freopen("bellmanford.out","w",stdout);
	if(ciclu_neg)
		printf("Ciclu negativ!\n");
	else{
		for(int i=2;i<=n;++i)
			printf("%d ",d[i]);
		printf("\n");
	}
}