#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define NMAX 50010
#define LMAX 250000000

int n,m;
vector < pair<int,int> > g[NMAX];
int dist[NMAX],uz[NMAX];
queue <int> q;
int ciclu_negativ;
bool inq[NMAX];

void read()
{
	int i,x,y,z;

	ifstream fin("bellmanford.in");

	fin>>n>>m;
	for (i=1; i<=m; ++i)
	{
		fin>>x>>y>>z;
		g[x].push_back( make_pair(y,z) );
	}

	fin.close();
}

void bellmanford()
{
	vector < pair<int,int> > :: iterator it;
	int elem,i;

	for (i=2; i<=n; ++i)
		dist[i] = LMAX;

	q.push(1);
	while (!q.empty())
	{
		elem = q.front();
		for (it=g[elem].begin(); it!=g[elem].end(); ++it)
			if (dist[it -> first] > dist[elem] + it -> second)
			{
				dist[it -> first] = dist[elem] + it -> second;
				uz[it -> first] ++;

				if (uz[it -> first] == n)
				{
					ciclu_negativ = 1;
					return;
				}

				if (inq[it -> first] == 0)
				{
					q.push(it -> first);
					inq[it -> first] = 1;
				}
			}
		inq[elem] = 0;
		q.pop();
	}
}

void write()
{
	int i;

	ofstream fout("bellmanford.out");

	if (ciclu_negativ == 1)
		fout<<"Ciclu negativ!";
	else
		for (i=2; i<=n; ++i)
			fout<<dist[i]<<" ";
	fout<<'\n';

	fout.close();
}

int main()
{

	read();
	bellmanford();
	write();

	return 0;
}