#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 bs(int in, int sf, int x)
{
	int m = (in + sf) / 2;
	if (a[m].x == x)return m;
	else if (a[m].x > x)sf = m - 1;
	else in = m + 1;
	return bs(in, sf, x);
}
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)
	{
		cnt++;
		x = c.front();
		c.pop();
		incoada[x] = 0;
		i = bs(1,m,x);
		while (a[i].x == x)i--;
		for (i+=1; 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] << " ";
}