#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct cua
{
	int y;
	int c;
	int d;
};
bool compa(cua a,cua b)
{
	if (a.c>b.c)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
vector<cua> g;
int distantaminima[50001];
cua sablon;
vector<cua> drumuri[50001];
int main()
{
	ifstream in("bellmanford.in");
	ofstream out("bellmanford.out");
	int i, n, m, x,j,d,c,y;
	in >> n;
	in >> m;
	sablon.d = 1;
	for (i = 1; i <= n; i++)
	{
		distantaminima[i] = 999999;
	}
	distantaminima[1] = 0;
	for (i = 1; i <= m; i++)
	{
		in >> x;
		in >> sablon.y;
		in >> sablon.c;
		drumuri[x].push_back(sablon);
	}
	for (i = 0; i < drumuri[1].size(); i++)
	{
		sablon.y = drumuri[1][i].y;
		sablon.c = drumuri[1][i].c;
		sablon.d = 1;
		g.push_back(sablon);
	}
	make_heap(g.begin(), g.end(), compa);
	while (g.size()>0)
	{
		d = g[0].d;
		c = g[0].c;
		y = g[0].y;
		pop_heap(g.begin(), g.end(), compa);
		g.pop_back();
		if (d == n)
		{
			out << "Ciclu negativ!";
			return 0;
		}
		if (c < distantaminima[y])
		{
			distantaminima[y] = c;
			j = g.size();
			for (i = 0; i < drumuri[y].size(); i++)
			{
				sablon.d = d + 1;
				sablon.c = c + drumuri[y][i].c;
				sablon.y = drumuri[y][i].y;
				g.push_back(sablon);
			}
			for (i = j; i < g.size(); i++)
				push_heap(g.begin(), next(g.begin(),i+1) , compa);
		}
	}
	for (i = 2; i <= n; i++)
	{
		out << distantaminima[i] << " ";
	}
}