#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;

const int kNmax = 50005;
ofstream fout("bellmanford.out");

using std::queue;
vector<int> v(kNmax, 1<<30);
vector<int> d(kNmax, 1<<30);

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

private:
	int n;
	int m;
	int source;
	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();
	}

	bool get_result() {
		/*
		TODO: Gasiti distantele minime de la nodul source la celelalte noduri
		folosind BellmanFord pe graful orientat cu n noduri, m arce stocat in adj.
			d[node] = costul minim / lungimea minima a unui drum de la source la nodul
		node;
			d[source] = 0;
			d[node] = -1, daca nu se poate ajunge de la source la node.

		Atentie:
		O muchie este tinuta ca o pereche (nod adiacent, cost muchie):
			adj[x][i].first = nodul adiacent lui x,
			adj[x][i].second = costul.

		In cazul in care exista ciclu de cost negativ, returnati un vector gol:
			return vector<int>();
		*/
        // int i, j;
        source = 1;
		d[source] = 0;

		queue<int> q;
		q.push(source);

		while (!q.empty()) {
		    int node = q.front();
		    q.pop();
		    v[node]++;
		    if (v[node] == n) {
                return true;
		    }
		    for (auto& i : adj[node]) {
		        if (d[i.first] > d[node] + i.second) {
		            d[i.first] = d[node] + i.second;
		            q.push(i.first);
		        }
		    }
		}

        return false;
		// return d;
	}

	void print_output(bool result) {
		if (result) {
			fout << "Ciclu negativ!\n";
		} else {
			for (int i = 2; i <= n; i++) {
				fout << d[i] << ' ';
			}
			fout << '\n';
		}
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}