#include<fstream>
#include<algorithm>]
#include<queue>
#define INF 100000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int d[50001], incoada[50001];
queue<int> c;
struct pizza
{
	int x, y, v;
}a[250001];
bool cmp(pizza a, pizza b)
{
	if (a.x < b.x)
		return 1;
	return 0;
}
int main()
{
	int i, p, u, x;
	long long cnt=0,n,m;
	f >> n >> m;
	for (i = 1; i <= m; i++)
		f >> a[i].x >> a[i].y >> a[i].v;
	sort(&a[1],&a[m + 1], cmp);
	for (i = 1; i <= n; i++)
		d[i] = INF;
	p = u = 1;
	c.push(1);
	incoada[1] = 1;
	d[1] = 0;
	while (!c.empty() && cnt<=n*m+1)
	{
		cnt++;
		x = c.front();
		c.pop();
		incoada[x] = 0;
		i = 1;
		while (a[i].x < x)i++;
		for (; a[i].x == x; i++)
		{
			if (d[x] + a[i].v < d[a[i].y])
			{
				d[a[i].y] = d[x] + a[i].v;
				if (!incoada[a[i].y])
				{
					c.push(a[i].y);
					incoada[a[i].y] = 1;
				}
			}
		}
	}
	if (cnt == n *m+1)
		g << "Ciclu negativ!";
	else 
	for (i = 2; i <= n; i++)
		g << d[i] << " ";
}