#include <fstream>
#include <vector>
#include <queue>
#define INF 1<<30

std::ifstream f("bellmanford.in");
std::ofstream g("bellmanford.out");

#define makeNode(a,b) std::make_pair(a, b)
typedef std::pair<int, int> Node;

class Graph {
private:
	int V;
	std::vector<Node> *table;

public:
	Graph(int V) {
		this->V = V;
		table = new std::vector<Node>[V];
	}

	void addEdge(int x, int y, int cost) {
		table[x].push_back(makeNode(y, cost));
	}

	void BF(int source) {

		std::queue<int> q;
		std::vector<int> costs(V, INF);
		std::vector<int> nrUsed(V, 0);
		std::vector<bool> isUsed(V, 0);

		int necessary = V - 1;

		q.push(source);
		isUsed[source] = true;
		costs[source] = 0;

		while (!q.empty()) {
			int node = q.front();
			q.pop();
			nrUsed[node]++;

			if (nrUsed[node] == necessary) {
				g << "Ciclu negativ!\n";
				return;
			}

			std::vector<Node>::iterator it;
			for (it = table[node].begin(); it != table[node].end(); ++it) {
				int vertex = it->first;
				int cost = it->second;

				int newCost = costs[node] + cost;

				if (costs[vertex] > newCost) {
					costs[vertex] = newCost;

					if (!isUsed[vertex]) {
						isUsed[vertex] = true;
						q.push(vertex);
					}

				}

			}
			isUsed[node] = false;
		}

		std::vector<int>::iterator it;
		for (it = costs.begin() + 2; it != costs.end(); ++it)
			g << *it << " ";
		g << '\n';

	}


};

int main() {
	int n;
	f >> n;

	int m;
	f >> m;

	Graph* myGraph = new Graph(n + 1);

	int x, y, cost;
	for (int i = 1; i <= m; ++i) {
		f >> x >> y >> cost;
		myGraph->addEdge(x, y, cost);
	}

	myGraph->BF(1);

	return 0;
}