///BEALLMAN_FORD
#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#include <limits>
#include <queue>

using namespace std;

typedef pair<int, unsigned> NODE;
typedef numeric_limits<int> I_LIM;

void bellmanFord(vector<list<NODE> >& adjList,
		vector<int>& output, bool& isNegativeCycle) {
	unsigned numNodes = adjList.size();
	queue<unsigned> q;
	vector<bool> isInQueue(numNodes, false);
	vector<unsigned> countQueue(numNodes, 0);

	q.push(0);
	output[0] = 0;

	list<NODE>::iterator it;
	unsigned current;
	while(!q.empty() && !isNegativeCycle) {
		current = q.front();
		q.pop();

		for(it = adjList[current].begin(); it != adjList[current].end(); it++)
			if(output[current] + it->first < output[it->second]) {
				output[it->second] = output[current] + it->first;

				if(!isInQueue[it->second])
					if(countQueue[it->second] > numNodes)
						isNegativeCycle = true;
					else {
						q.push(it->second);
						isInQueue[it->second] = true;
						countQueue[it->second]++;
					}

			}
	}
}

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

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

	vector<list<NODE> > adjList(numNodes);
	vector<int> output(numNodes, I_LIM::max());
	bool isNegativeCycle = false;

	unsigned from, to;
	int cost;
	for(unsigned i=0; i < numEdges; i++) {
		inStr >> from >> to >> cost;
		adjList[--from].push_back(NODE(cost, --to));
	}

	bellmanFord(adjList, output, isNegativeCycle);

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

	return 0;
}