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

using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;
using std::set;
using std::pair;
using std::queue;

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


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

	void read() {
		ifstream in(input_file);

		in >> n >> m;
		distance.resize(n + 1, oo);
		viz.resize(n + 1, false);
		number.resize(n + 1, 0);
		graf = new vector<arc>[n + 1];

		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();

		queue<int> q;
		q.push(source);
		distance[source] = 0;
		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:
	Solve(const string& input_file, const string& output_file, int source) : input_file{ input_file }, output_file{ output_file }, source{ source }{};

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


		out.close();
	}

	~Solve() {
		delete[] graf;
	}
};

int main() {

	Solve s = Solve("bellmanford.in", "bellmanford.out", 1);
	s.print();

	return 0;
}