#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define f first
#define s second 
#define NMAX 50003
#define in "bellmanford.in"
#define out "bellmanford.out"
#define mp make_pair
#define pb push_back
#define INF 100000000

ifstream fin(in);
ofstream fout(out);

vector<pair<int,int> > g[NMAX];
queue<int> Q;
bool used[NMAX];

int main()
{
	int i,N,M,x,y,z;
	
	fin>>N>>M;
	
	for(i = 1; i <= M; i++)
	{
		fin>>x>>y>>z;
		g[x].pb(mp(y,z));
	}
	
	vector<int> dist(NMAX,INF);;
	vector<int> cntUsed(NMAX,0);
	
	used[1] = true;
	dist[1] = 0;
	Q.push(1);
	
	bool negativeCycle = false;
	int node;
	vector<pair<int,int> >::iterator it;
	
	while(!Q.empty() && !negativeCycle)
	{
		x = Q.front();
		Q.pop();
		used[x] = 0;
		for(it = g[x].begin(); it != g[x].end(); it++)
			if(dist[it->f] > dist[x] + it->s)
				{
					dist[it->f] = dist[x] + it->s;
					if(!used[it->f])
						if(cntUsed[it->f] > N)
							negativeCycle = true;
						else
						{
							Q.push(it->f);
							used[it->f] = 1;
							cntUsed[it->f]++;
						}
				}
	}
	
	if(negativeCycle == true)
		fout<<"Ciclu negativ\n";
	else
		{
			for(int i = 2; i <= N; i++)
				fout<<dist[i]<<' ';
			fout<<'\n';
		}

	fin.close();
	fout.close();
	return 0;
}