#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50010
#define INF 1e9
using namespace std;

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

vector<pair<int,int>>G[NMAX];

int main()
{
	int n, m;
	fin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		int x, y, cost;
		fin >> x >> y >> cost;
		G[x].push_back(make_pair(y,cost));
	}

	vector<int>dist(n+2, INF);
	dist[1] = 0;

	vector<int>viz(n+2, 0);
	viz[1]++;

	queue<int> q;
	q.push(1);

	bool ok = 1;
	while(q.size())
	{
		int nod = q.front();
		q.pop();

		vector<pair<int,int>>::iterator it;
		for(it = G[nod].begin(); it != G[nod].end(); it++)
		{
			int cost = it->second;
			int nod1 = it->first;

			if(dist[nod1] > dist[nod] + cost)
			{
				dist[nod1] = dist[nod] + cost;
				viz[nod1]++;
				q.push(nod1);

				if(viz[nod1] == n-1)
				{
					ok = 0;
					break;
				}
			}
		}
		if(ok == 0)
		{
			break;
		}
	}
	if(ok == 0)
	{
		fout << "Ciclu negativ!";
	}
	else
	{
		for(int i = 2; i <= n; i++)
		{
			fout << dist[i] << " ";
		}
	}

	fin.close();
	fout.close();
	return 0;
}