#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <queue>
#include <cmath>
using namespace std;

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

#define NMAX 50005
const char msg[] = "Ciclu negativ!";

struct ST{
	int y;
	int cost;
};

vector<ST> adj[NMAX];
int n, m;
double dist[NMAX];

void read()
{
	in >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		
		adj[x].push_back({ y,c });
	}

	for (int i = 0; i <= n+1; i++)
		dist[i] = INFINITY;
}

void bellman()
{
	dist[1] = 0; // starting from node 1

	for (int k = 0; k < n - 1; k++)
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < adj[i].size(); j++)
			{
				if (dist[i] + adj[i][j].cost < dist[adj[i][j].y])
					dist[adj[i][j].y] = dist[i] + adj[i][j].cost;
			}
		}

	for (int k = 0; k < n - 1; k++)
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < adj[i].size(); j++)
			{
				if (dist[i] + adj[i][j].cost < dist[adj[i][j].y])
				{
					//dist[adj[i][j].y] = -INFINITY; if we need to mark negative cycles

					// in this case we need just to print a msg if we have a negative cycle
					out << msg;
					return;
				}
			}
		}

	for (int i = 2; i <= n; i++) // printing the distances to all the nodes from node 1
		out << dist[i] << ' ';
}

int main()
{
	read();
	bellman();
}