#define DM 50001
#define inf 0x3f3f3f3f
#define n first
#define cst second
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;

ifstream fi ("bellmanford.in");
ofstream fo ("bellmanford.out");
int n, m, a, b, c, dst[DM], vf[DM];
vector <pair <int, int> > v[DM];

int main()
{
	fi >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		fi >> a >> b >> c;
		v[a].push_back({b, c});
	}
	memset(dst, inf, sizeof(dst));
	dst[1] = 0;
	for (int i = 1; i < n; ++i)
		for (int j = 1; j <= n; ++j)
			for (auto k:v[j])
				if (dst[k.n] > dst[j] + k.cst)
					dst[k.n] = dst[j] + k.cst;
	for (int i = 1; i <= n; ++i)
		vf[i] = dst[i];
	for (int i = 1; i <= n; ++i)
		for (auto j:v[i])
			if (vf[j.n] > vf[i] + j.cst)
				vf[j.n] = vf[i] + j.cst;
	for (int i = 1; i <= n; ++i)
		if (vf[i] != dst[i])
		{
			fo << "Ciclu negativ!";
			return 0;
		}
	for (int i = 2; i <= n; ++i)
			fo << dst[i] << ' ';
	return 0;
}