#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>

using namespace std;

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

#define INFTY 10000000

vector < vector < pair <int, int> > > edge;
vector <int> dist;
int N,M;

int bellman_ford (int node)
{
	queue <int> NodeQ;
	int used[N], negative_Cycle = 0;
	vector <int> noInQfor;
	noInQfor.resize(N+1);
	fill (used+1, used+N+1, 0);
	fill(noInQfor.begin(), noInQfor.begin()+N+1,0);

	NodeQ.push(node);
	dist[node] = 0;
	used[node] = 1;

	while (!NodeQ.empty() && !negative_Cycle)
	{
		node = NodeQ.front();
		NodeQ.pop();
		used[node] = 0;
		for (int i = 0; i < edge[node].size(); ++i)
			if (dist[node] < INFTY)
			if (dist[edge[node][i].first] > dist[node] + edge[node][i].second)
			{
				dist[edge[node][i].first] = dist[node] + edge[node][i].second;
				if (!used[edge[node][i].first])
					if (noInQfor[edge[node][i].first] > N)
						negative_Cycle = 1;
					else
					{
						NodeQ.push(edge[node][i].first);
						used[edge[node][i].first] = 1;
						++noInQfor[edge[node][i].first];
					}
			}
	}
	return negative_Cycle;
}

int main()
{
    fin >>N >>M;
    edge.resize(N+1);
    dist.resize(N+1);
    fill(dist.begin(), dist.begin()+N+1,INFTY);
    for (int i = 1; i < M; ++i)
	{
		int x,y,c;
		fin >>x >>y >>c;
		edge[x].push_back(make_pair(y,c));
	}

	if (bellman_ford(1))
		fout <<"Ciclu negativ!";
	else
		for (int i = 2; i <= N; ++i)
			fout <<dist[i] <<' ' ;
	fout <<'\n';
    return 0;
}