#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

struct node_pair
{
	int a;
	int b;
};

struct edge
{
	int node;
	vector<node_pair> adj;
};

int main(void)
{
	ifstream inp("bellmanford.in");
	ofstream out("bellmanford.out");

	int n, m;

	inp >> n >> m;

	struct edge *nodes = new struct edge[n + 1];
	for(int i = 0; i < m; i++)
	{
		int x, y, c;
		inp >> x >> y >> c;

		struct node_pair np = {y, c};

		nodes[x].adj.push_back(np);
	}

	int *d = new int[n + 1];
	int start = 1;
	const int inf = 2317896;

	memset(d, inf, sizeof(int) * (n + 1));
	d[start] = 0;

	// aplicam bellman ford simplu
#if 0
	bool end = false;
	while(!end)
	{
		end = true;
		for(int i = 1; i <= n; i++)
		{
			for(int j = 0, len = nodes[i].adj.size(); j < len; j++)
			{
				int cost = nodes[i].adj[j].b;
				if(d[i] + cost < d[nodes[i].adj[j].a])
				{
					d[nodes[i].adj[j].a] = d[i] + cost;
					end = false;
				}
			}
		}
	}
#endif

	queue<int> q;
	int *count = new int[n + 1];
	bool *inq = new bool[n + 1];
	memset(inq, false, sizeof(bool) * (n + 1));
	memset(count, 0, sizeof(int) * (n + 1));

	count[start] = 1;
	inq[start] = true;
	q.push(start);

	bool has_negative_cycle = false;
	while(!q.empty() && !has_negative_cycle)
	{
		int p = q.front();
		q.pop();
		inq[p] = false;

		for(int i = 0, len = nodes[p].adj.size(); i < len; i++)
		{
			if(d[p] + nodes[p].adj[i].b < d[nodes[p].adj[i].a])
			{
				d[nodes[p].adj[i].a] = d[p] + nodes[p].adj[i].b;
				if(!inq[nodes[p].adj[i].a])
				{
					if(count[nodes[p].adj[i].a] > n)
					{
						has_negative_cycle = true;
					}
					else
					{
						inq[nodes[p].adj[i].a] = true;
						count[nodes[p].adj[i].a]++;
						q.push(nodes[p].adj[i].a);
					}
				}
			}
		}
	}

	if(has_negative_cycle)
		out << "Ciclu negativ!";
	else
	{
		for(int i = 2; i <= n; i++)
			out << d[i] << " ";
	}

	delete[] inq;
	delete[] count;
	delete[] d;
	delete[] nodes;
	inp.close();
	out.close();

	system("pause");
	return 0;
}