#include<iostream>
#include<queue>
#include<vector>
#define lim 50005
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int, int> pii;
vector<pii> g[lim];
queue<int> q;
bool inQ[lim];
int n, m, d[lim], viz[lim];

bool bf(int src)
{
	d[src] = 0, inQ[src] = true;
	q.push(src);
	while (!q.empty())
	{
		int nod = q.front();
		q.pop();
		viz[nod]++, inQ[nod] = false;
		if (viz[nod] >= n)
			return false;
		for (auto it : g[nod])
		{
			int vec = it.first, cost = it.second;
			if (d[nod] + cost < d[vec])
			{
				d[vec] = d[nod] + cost;
				if (!inQ[vec])
				{
					q.push(vec);
					inQ[vec] = true;
				}
			}
		}
	}
	return true;
}


int main()
{
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		cin >> x >> y >> c;
		g[x].push_back({ y,c });
	}
	for (int i = 1; i <= n; i++)
		d[i] = inf;

	if (!bf(1))
		cout << "Ciclu negativ!";
	else
		for (int i = 2; i <= n; i++)
			cout << d[i] << " ";
}