#include <iostream>
#include <vector>
#include <utility>
#include <fstream>

using namespace std;

#define maxn 50010
#define maxm 250010
#define INF 1000000000

typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<vector<pair<int, int>>> vvii;

struct muchie {
	long a, b, c;

	muchie(int a, int b, int c) : a(a), b(b), c(c) {};
};

class Graph {

public:
	Graph(string s) {
		ifstream iff(s);
		iff >> N >> M;;
		
		for (int i = 0; i < M; ++i) {
			long a, b, c;
			iff >> a >> b >> c;
			G.push_back(muchie(a, b, c));
		}
		
	}

	void bellmann(int s, string out) {
		ofstream off(out);

		vector<long> d(N + 1, INF);
		d[s] = 0;

		for (int i = 1; i <= N; ++i) {
			for (auto m : G) {


				if (d[m.b] > d[m.a] + m.c) {
					d[m.b] = d[m.a] + m.c;
				}
			}
		}

		bool ciclu = false;
		for (int i = 1; i <= N; ++i) {
			if (ciclu) {
				break;
			}
			for (auto m : G) {
				if (d[m.a] + m.c < d[m.b]) {
					off << "Ciclu negativ!\n" << endl;
					ciclu = true;
					break;
				}
			}
		}

		if (!ciclu) {
			for (int i = 2; i <= N; ++i) {
				off << d[i] << " ";
			}
			off << endl;
		}
	}

private:
	vector<muchie> G;
	int N, M;
};

int main() {
	Graph g("bellmanford.in");
	g.bellmann(1, "bellmanford.out");

	return 0;
}