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

const int kNmax = 50005;
const int kInf = 0x3f3f3f3f;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	int source = 1;
	vector<pair<int, int> > adj[kNmax];

	void read_input() {
		ifstream fin("bellmanford.in");
		fin >> n >> m;
		for (int i = 1, x, y, w; i <= m; i++) {
			fin >> x >> y >> w;
			adj[x].push_back(make_pair(y, w));
		}
		fin.close();
	}

	vector<int> get_result() {
		vector<int> d(n + 1, kInf);
		vector<int> selected(n + 1, false);
		vector<int> modified(n + 1, 0);
		queue<int> q;
		vector<int> empty;

		d[0] = 0;
		d[source] = 0;
		q.push(source);
		selected[source] = true;
		int u, v, weight;

		while(!q.empty()) {
			u = q.front();
			q.pop();
			selected[u] = false;
			for (auto pair: adj[u]) {
				v = pair.first; weight = pair.second;
				if (d[v] > d[u] + weight) {
					d[v] = d[u] + weight;
					if (selected[v] == false) {
						selected[v] = true;
						q.push(v);
					}

					modified[v]++;
					if (modified[v] > n) {
						return empty;
					}
				}
			}
		}

		for (int i = 0; i <= n; i++) {
			if (d[i] == kInf) {
				d[i] = -1;
			}
		}

		return d;
	}

	void print_output(vector<int> result) {
		ofstream fout("bellmanford.out");
		if (result.size() == 0) {
			fout << "Ciclu negativ!\n";
		} else {
			for (int i = 2; i <= n; i++) {
				fout << result[i] << ' ';
			}
			fout << '\n';
		}
		fout.close();
	}
};

// Please always keep this simple main function!
int main() {
	// Allocate a Task object on heap in order to be able to
	// declare huge static-allocated data structures inside the class.
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}