#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define mp make_pair
#define nod first
#define cost second

char buf[100000];
int n, m;
vector<vector<pair<int, int> > > a;
vector<int> d;

bool bellmanford()
{
	d.clear();
	d.resize(n + 1, 0x7fffffff);
	queue<int> q;
	char *viz = new char[n+1];
	int v;

	d[1] = 0;
	for(int iter=1;iter<n;++iter)
	{
		memset(viz, 0, n + 1);
		while(!q.empty())
			q.pop();
		q.push(1);
		viz[1] = 1;
		while(!q.empty())
		{
			v = q.front(); q.pop();
			for(vector<pair<int, int> >::iterator it = a[v].begin(); it != a[v].end(); ++ it)
				if (!viz[it->nod] && d[it->nod] > d[v] + it->cost)
				{
					d[it->nod] = d[v] + it->cost;
					viz[it->nod] = 1;
					q.push(it->nod);
				}
		}
	}

	delete viz;
	for(int i=1;i<=n;++i)
		for(vector<pair<int, int> >::iterator it = a[i].begin(); it != a[i].end(); ++ it)
			if(d[it->nod] > d[i] + it->cost)
				return false;
	return true;
}

int main()
{
	ifstream fin("bellmanford.in");
	fin.rdbuf()->pubsetbuf(buf, 100000);
	ofstream fout("bellmanford.out");

	fin >> n >> m;
	a.resize(n + 1);
	int x, y, c;
	while(--m)
	{
		fin >> x >> y >> c;
		a[x].push_back(mp(y, c));
	}

	if (bellmanford())
	{
		for(int i=2;i<=n;++i)
			fout << d[i] << " ";
		fout << endl;
	}
	else
		fout << "Ciclu negativ!" << endl;

	return 0;
}