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

using namespace std;
fstream fin("bellmanford.in", ios::in);
fstream fout("bellmanford.out", ios::out);
#define MAXN 50000
#define INF 0x3f3f3f3f

int n, used[MAXN], d[MAXN];
vector <pair<int,int>> list[MAXN];
queue <int> q;

void read()
{
	int x, y, c, m;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
		fin >> x >> y >> c,
		list[x].push_back(make_pair(y, c));
}
int bellman_ford()
{
	q.push(1);
	for (int i = 1; i <= n; i++)
		d[i] = INF;
	d[1] = 0;
	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		if (++used[node] == n)
			return 0;
		for (int i = 0; i < list[node].size(); i++)
			if (d[list[node][i].first] > d[node] + list[node][i].second)
				q.push(list[node][i].first),
				d[list[node][i].first] = d[node] + list[node][i].second;
	}
	return 1;
}

int main()
{
	read();
	if (bellman_ford())
		for (int i = 1; i < n; i++, fout << d[i] << ' ');
	else fout << "Ciclu negativ!";

	fin.close();
	fout.close();
	return 0;
}