///BELLMAN-FORD
#include <fstream>
#include <vector>
#include <list>
#include <limits>
using namespace std;

typedef numeric_limits<int> I_LIM;

struct EDGE {
	unsigned from, to;
	int cost;
};

void bellmanFord(list<EDGE>& edges, vector<int>& distances, bool isNegativeCycle) {
	for(unsigned i=0; i < distances.size(); i++)
		distances[i] = I_LIM::max();
	distances[0] = 0;

	list<EDGE>::iterator it;
	for(unsigned i=0; i < distances.size() - 1; i++)
		for(it = edges.begin(); it != edges.end(); it++)
			if(distances[it->to] > distances[it->from] + it->cost)
				distances[it->to] = distances[it->from] + it->cost;

	///test the negative cycles
	for(it = edges.begin(); it != edges.end(); it++)
		if(distances[it->to] > distances[it->from] + it->cost)
			isNegativeCycle = true;
}

int main() {
	ifstream inStr("bellmanford.in");
	ofstream outStr("bellmanford.out");

	unsigned numNodes, numEdges;
	inStr >> numNodes >> numEdges;

	vector<int> distances(numNodes);
	list<EDGE> edges;
	bool isNegativeCycle = false;

	EDGE temp;
	for(unsigned i=0; i < numEdges; i++) {
		inStr >> temp.from >> temp.to >> temp.cost;
		--temp.from; --temp.to;
		edges.push_back(temp);
	}

	bellmanFord(edges, distances, isNegativeCycle);

	if(isNegativeCycle)
		outStr << "Ciclu negativ!";
	else
		for(unsigned i=1; i < numNodes; i++)
			outStr << distances[i] << ' ';
	outStr << '\n';

	return 0;
}