#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

const int NMAX = 50005, inf = (1 << 30);
int n, m;
vector<vector<pair<int, int>>> v;
vector<int> d;

bool spfa(int start)
{
	d.assign(n + 1, inf);
	vector<int> oc(n + 1, 0);
	queue<int> q;
	bitset<NMAX> inqueue;
	d[start] = 0;
	q.push(start);
	inqueue[start] = 1;

	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		inqueue[p] = 0;
		for (int i = 1; i < v[p].size(); i++)
		{
			int la = v[p][i].first;
			int c = v[p][i].second;
			if (d[p] + c < d[la])
			{
				d[la] = d[p] + c;
				if (!inqueue[la])
				{
					q.push(la);
					inqueue[la] = 1;
					oc[la]++;
					if (oc[la] >= n)
						return false;
				}
			}
		}
	}
	return true;
}

int main()
{
	fi >> n >> m;
	for (int i = 1; i <= n + 1; i++)
	{
		vector<pair<int, int>> k;
		v.push_back(k);
		pair<int, int> l;
		l.first = 0;
		l.second = 0;
		v[i - 1].push_back(l);
	}
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		fi >> x >> y >> c;
		pair<int, int> k;
		v[x].push_back(k);
		v[x][v[x].size() - 1].first = y;
		v[x][v[x].size() - 1].second = c;
	}
	if (spfa(1))
	{
		for (int i = 2; i <= n; i++)
		{
			fo << d[i] << " ";
		}
	}
	else
		fo << "Ciclu negativ!";
}