#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;
	vector<int> cnt(n + 1, 0);
	char *viz = new char[n+1];
	int v;
	bool ret = true;

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

	delete viz;
	return ret;
}

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;
}