#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
#define N 50005
#define inf 0x3f3f3f3f
#define val first
#define cost second
#define iter vector<pair<int, int> >::iterator

using namespace std;

int D[N];

struct Comparator
{
	bool operator()(int a, int b)
	{
		return D[a] > D[b];
	}
};

vector<pair<int, int> > L[N];
priority_queue<int, vector<int>, Comparator> Q;
bitset<N> E;

int main()
{
	int n, m, x, y ,c, node;
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	memset(D, inf, sizeof(D));
	D[1] = 0;
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y >> c;
		L[x].push_back(make_pair(y, c));
	}

	int j;
	for (int i = 0; i < n; ++i)
	{
		Q.push(1);
		for (j = 0; !Q.empty() && j < 4; ++j)
		{
			node = Q.top();
			E[node].flip();
			Q.pop();
			for (iter it = L[node].begin(); it != L[node].end(); ++it)
				if (D[node] + it->cost < D[it->val])
				{
					D[it->val] = D[node] + it->cost;
					if (!E[it->val])
					{
						Q.push(it->val);
						E[it->val].flip();
					}
				}
		}
	}

	for (int i = 1; i <= n; ++i)
		for (iter it = L[i].begin(); it != L[i].end(); ++it)
			if (D[i] + it -> cost < D[it -> val])
			{
				fout << "Ciclu negativ!\n";
				return 0;
			}

	for (int i = 2; i <= n; ++i)
		fout << (D[i] == inf ? 0 : D[i]) << ' ';
	fout << '\n';

    return 0;
}