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

const int COST_MAX = 999999999;
const int NOD_MAX = 50000;

struct Pair {
	int nod, cost;
	Pair(int nod = 0, int cost = 0) : nod(nod), cost(cost) {}
};

std::vector<Pair> graf[NOD_MAX];
std::queue<int> coada;
int dist[NOD_MAX], viz[NOD_MAX];
int n = 0, m = 0;

bool bellman_ford()
{
	for(int i = 1; i < n; i++)
		dist[i] = COST_MAX;

	coada.push(0);

	while(!coada.empty())
	{
		int x = coada.front();
		coada.pop();

		if(viz[x] >= n)
			return false;

		viz[x]++;
		for(size_t i = 0; i < graf[x].size(); i++)
		{
			int v = graf[x][i].nod;
			int c = graf[x][i].cost;

			if(dist[v] > dist[x] + c)
			{
				dist[v] = dist[x] + c;
				coada.push(v);
			}
		}
	}

	return true;
}

int main()
{
	std::ifstream fin("bellmanford.in");
	std::ofstream fout("bellmanford.out");
	if(!fin.is_open() || !fout.is_open())
		return -1;

	int a = 0, b = 0, c = 0;

	fin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		fin >> a >> b >> c;
		graf[a - 1].push_back(Pair(b - 1, c));
	}

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