#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;

class Task {
public:
	void solve() {
		read_input();
		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 B_Ford() {
        source = 1;

        for (int i = 1; i <= n; i++) {
            d[i] = 1<<30;
        }
        d[source] = 0;
        queue<int> q;
        q.push(source);

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

	void 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;
        if (B_Ford()) {
            fout << "Ciclu negativ!\n";
        } else {
            print_output();
        }

		// return d;
	}

	void print_output() {
	    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;
}