#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005
#define INF 999999

using namespace std;

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

struct pairs
{
	int nod;
	int cost;
	pairs(int a = 0, int b = 0)
	{
		nod = a;
		cost = b;
	}
};


vector<pairs> g[NMAX];
int distante[NMAX];
queue<int> q;
int ap[NMAX];
/*struct comp
{
	bool operator()(int a, int b)
	{
		return(distante[a] > distante[b]);
	}
};
priority_queue<int, vector<int>, comp>q;*/

int inQueue[NMAX];
int ap[NMAX];
int n, m;



void print()
{
	for (int i = 2; i <= n; i++)
	{
		o << distante[i] << " ";
	}
}

bool bellman(int st)
{
	for (int i = 1; i <= n; i++)
	{
		distante[i] = INF;
	}
	distante[st] = 0;
	q.push(st);
	inQueue[st] = 1;
	ap[st]++;
	while (!q.empty())
	{
		int current = q.back();
		q.pop();
		inQueue[current] = 0;
		for (int i = 0; i < g[current].size(); i++)
		{
			int vf = g[current][i].nod;
			int c = g[current][i].cost;
			if (distante[current] + c < distante[vf])
			{
				distante[vf] = distante[current] + c;
				if (!inQueue[vf])
				{
					ap[current]++;
					if (ap[current] == n)
						return false;
					q.push(vf);
					inQueue[vf] = 1;
				}
			}
		}
	}
	return true;
}

int main()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		f >> x >> y >> c;
		g[x].push_back(pairs(y, c));
	}
	
	bellman(1);
	if (bellman(1))
		print();
	else
		o << "Ciclu negativ!";
}