#include <vector>
#include <fstream>
#include <string>
#include <queue>

#define arc pair<int, int>
#define nod first
#define cost second
#define oo 0x3f3f3f3f

using std::vector;
using std::pair;

std::ifstream in("bellman.in");
std::ofstream out("bellman.in");

class Bellman {
private:
	int n, m, source;
	vector<arc>* graf;
	std::string input_file;
	std::string output_file;
	vector<int> number, distance;
	vector<bool> viz;

	void read() {
		std::ifstream in(input_file);
		in >> n >> m;
		
		graf = new vector<arc>[n + 1];
		number.resize(n + 1, 0);
		distance.resize(n + 1, oo);
		viz.resize(n + 1, false);

		int x, y, w;
		for (int i = 1; i <= m; ++i) {
			in >> x >> y >> w;
			graf[x].push_back(std::make_pair(y, w));
		}

		in.close();
	}

	bool solve() {
		read();
		distance[source] = 0;
		std::queue<int> q;
		q.push(source);
		viz[source] = true;

		while (!q.empty()) {
			int node = q.front();

			for (auto muchie : graf[node]) {
				if (distance[muchie.nod] > distance[node] + muchie.cost) {
					distance[muchie.nod] = distance[node] + muchie.cost;
					if (!viz[muchie.nod]) {
						q.push(muchie.nod);
					}

					viz[muchie.nod] = true;
					number[muchie.nod]++;
					if (number[muchie.nod] >= n) {
						return false;
					}
				}
			}

			viz[node] = false;
			q.pop();
		}

		return true;
	}

public:
	Bellman(const std::string& input, const std::string& output) : input_file{ input }, output_file{ output }, source{ 1 }{};

	~Bellman() {
		delete[] graf;
	}

	void print() {
		std::ofstream out(output_file);
		if (solve()) {
			for (int i = 2; i <= n; ++i) {
				out << distance[i] << " ";
			}
		}
		else {
			out << "Ciclu negativ!";
		}

		out.close();
	}
};

int main() {
	Bellman b = Bellman{"bellmanford.in", "bellmanford.out"};
	b.print();

	return 0;
}