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

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

using std::queue;

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

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

    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;
        d.resize(n + 1, 1<<30);
        v.resize(n + 1);
        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;
}