#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<  pair<int, long long>   > v[50002];
//         vf,    cost

long long d[50002];
queue <int> q; // bag in q nodurile la care fac imbunatatire
int cnt[50002], inqueue[50002];
int main()
{
	int n,m, a, b, c;
	fin>>n>>m;
	for(int i=1; i<=m; i++) {
		fin>>a>>b>>c; // a--cost c->b
		v[a].push_back( make_pair(b, c) );

	}


	for(int i=1; i<=n; i++) {
		d[i] = INF;
	}
	d[1]=0;
	q.push(1);
	inqueue[1]=1;
	cnt[1]=1;
	int amcircuitnegativ=0;




	while( !q.empty() && amcircuitnegativ==0 ) {
		int vf = q.front();
		inqueue[vf] = 0;
		q.pop();
		for(vector<pair<int, long long>> :: iterator it = v[vf].begin(); it !=v[vf].end(); it++)
			if(d[vf]+it->second<d[it->first]) {
				d[it->first]=d[vf]+it->second;
				cnt[it->first]++;
				if(cnt[it->first]==n)amcircuitnegativ=1;
				if(inqueue[it->first]==0) {
					q.push(it->first);
					inqueue[it->first]=1;
				}
			}

	}



	if(amcircuitnegativ ) fout<<"Ciclu negativ!";
	else for(int i=2; i<=n; i++)fout<<d[i]<<' ';

	return 0;
}