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

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int nmax = 50001;
const int inf = 1294967296;
int n, m;

struct duo
{
	int adj, w;
};
vector <duo> ad[nmax];
int d[nmax], viz[nmax], nr[nmax];
queue<int> q;
void init(int s)
{
	for (int i = 1; i <= n; i++)
	{
		d[i] = inf;
	}
	d[s] = 0;
}


bool bellman(int s)
{
	init(s);
	q.push(s);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < ad[x].size(); i++)
		{
			if (d[ad[x][i].adj]>d[x] + ad[x][i].w)
			{
				d[ad[x][i].adj] = d[x] + ad[x][i].w;
				nr[ad[x][i].adj]++;
				q.push(ad[x][i].adj);
			}
			if (nr[ad[x][i].adj] > n)
				return 0;
		}
	}
	return 1;
}


int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x;
		duo h;
		fin >> x >> h.adj >> h.w;
		ad[x].push_back(h);
	}
	if (!bellman(1))
	{
		fout << "Ciclu negativ!";
	}
	else
	{
		for (int i = 2; i <= n; i++)
		{
			fout << d[i] << ' ';
		}
	}
}