#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

typedef pair<int, int> Node;
#define p first
#define c second

#define INF (1<<30)
#define MAX 50010

vector<Node> G[MAX];

queue<int> Q;

bitset<MAX> inQueue;

int relaxTimes[MAX],D[MAX], N, M;

bool bellmanford(int S)
{
	for (int i = 1; i <= N; ++i)
		D[i] = INF;
	Q.push(S);
	inQueue[S] = 1;
	D[S] = 0;

	while (Q.size())
	{
		int node = Q.front();
		Q.pop();
		inQueue[node] = 0;

		for (int i = 0; i < G[node].size();++i)
			if (D[node] + G[node][i].c < D[G[node][i].p])
			{
				D[G[node][i].p] = D[node] + G[node][i].c;
				if (inQueue[G[node][i].p]==0)
				{
					inQueue[G[node][i].p] = 1;
					Q.push(G[node][i].p);
					relaxTimes[G[node][i].p]++;
					if (relaxTimes[G[node][i].p] == N)
						return 1;

				}
			}

	}

	return 0;

}

int main()
{
	in >> N >> M;

	for (int i = 1; i <= M; ++i)
	{
		int x, y, cost;
		in >> x >> y >> cost;
		G[x].push_back(make_pair(y, cost));
	}

	if (bellmanford(1))
		out << "Ciclu negativ!";
	else
	{
		for (int i = 2; i <= N; ++i)
			out << D[i] << " ";
	}

	return 0;
}