#include <bits/stdc++.h>
using namespace std;

template <typename type>
class Graph {

public:

	struct Edge {	
		int from, to; 
		type cost; 
	};

	int n;
	vector<Edge> edg;
	vector<vector<int>> gph;

	Graph(int _n) : n(_n) {
		gph.resize(n); }
	
	virtual int addEdge(int from, int to, type cost = 1) {
		assert(0 <= min(from, to) and max(from, to) < n);
		int id = (int) edg.size();
		gph[from].push_back(id);
		edg.push_back({from, to, cost}); 
		return id; }
};

template <typename type>
vector<type> bellmanFord(const Graph<type> &g, vector<int> lst, const int lim = 1000000) {
	vector<type> dst(g.n, numeric_limits<type> :: max());
	deque<int> que; vector<bool> oki(g.n, false); int cnt = 0;
	for (int src : lst) {
		assert(0 <= src and src < g.n);
		dst[src] = 0; oki[src] = true; que.push_back(src); }
	while (que.size()) {
		int x = que.front(); oki[x] = false; que.pop_front();
		for (int id : g.gph[x]) {
			auto &ed = g.edg[id]; int y = ed.from ^ ed.to ^ x;
			if (dst[y] > dst[x] + ed.cost) {
				dst[y] = dst[x] + ed.cost;
				if (!oki[y]) {
					oki[y] = true; ++cnt; que.push_back(y);
					if (cnt == lim) {
						return vector<type>(); } } } } }
	return dst; }

template <typename type>
vector<type> bellmanFord(const Graph<type> &g, int src, const int lim = 1000000) {
	return bellmanFord(g, vector<int>(1, src), lim); }

/*
template <typename type>
class DirectedGraph : public Graph<type> {

public:

	using Graph<type> :: n;
	using Graph<type> :: gph;
	using Graph<type> :: edg;
	
	DirectedGraph(int _n) :
		Graph<type>(_n) {}

	int addEdge(int from, int to, type cost = 1) {
		assert(0 <= min(from, to) and max(from, to) < n);
		int id = (int) edg.size(); 
		gph[from].push_back(id);
		edg.push_back({from, to, cost}); 
		return id; }

	DirectedGraph<type> reverseGraph(void) {
		DirectedGraph<type> rvg(n);
		for (auto &ed : edg) {
			rvg.addEdge(ed.to, ed.from, ed.cost); }
		return rvg; }
};
 */

	
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
} in("bellmanford.in");

const int DIM = 50005;

Graph<int> g(DIM);

int main(void) {
//	freopen("dijkstra.in", "r", stdin); 
	freopen("bellmanford.out", "w", stdout);
	int n, m; in >> n >> m;
	while (m--) {
		int x, y, c; in >> x >> y >> c;
		g.addEdge(x, y, c); }
	vector<int> dst = bellmanFord(g, 1);
	if (dst == vector<int>()) {
		cout << "Ciclu negativ!"; }
	else {
		for (int i = 2; i <= n; ++i) {
			cout << dst[i] << " "; } }
	return 0; }