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

/*
    Algoritmul lui Bellman-Ford:
        - se aplica pe graf orientat, conex, care are si muchii cu costuri negative

    -------------------------------------------------------------------------------

        Algoritmul determina daca graful are lant de cost negativ, caz in care afiseaza
    in fisier un mesaj. Daca nu, atunci el afiseaza costurile minime de la sursa la toate
    celelalte noduri din graf.
        Algoritmul basic are complexitate temporala de O(n * m), insa poate fi optimizat
    folosind o queue sau o priorityqueue, avand complexitate de O(n * m), respectiv
    O(n * m * log(n)), insa, in practica, ele se comporta mult mai ok.
        Implementarea de fata utilizeaza o coada de prioritate si are implementate si
    metode de afisare a drumurilor minime.
*/

#define NMAX 50007
#define INF (1 << 30)
#define NO_PARENT -1

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

private:
    // numar de noduri
    int n;

    // numar de muchii
    int m;

    // vector de distante
    vector<int> dist;

    // vector de partinti folosit la reconstruirea path-ului
    vector<int> p;

    // liste de adiacenta
    vector<pair<int, int>> adj[NMAX];

    // sursa
    int source;

    // 
    bool foundNegativeCicle;

    void read_input() {
        ifstream fin("bellmanford.in");

        fin >> n >> m;

        dist.resize(n + 1);
        p.resize(n + 1);

        for (int i = 1; i <= m; ++i) {
            int x, y, cost;

            fin >> x >> y >> cost;

            adj[x].push_back({y, cost});

            // decomentezi daca vrei ca graful sa fie neorientat
            // adj[y].push_back({x, cost});
        }

        fin.close();
    }

    void get_result() {
        // modifici linia asta daca vrei alta sursa
        source = 1;

        // logica dijkstra din nodul source
        foundNegativeCicle = BellmanFord(source, dist, p);
    }

    // metoda intoarce 'true' daca a gasit ciclu de cost negativ; 'flase' altfel
    bool BellmanFord(int source, vector<int> &dist, vector<int> &p) {
        /*
            Min-heap ce va fi folosit pentru a stoca perechide tipul <distanta pana la sursa a nodului x, nodul x>.
            Este folosit pentru a extrage la fiecare pas nodul care are distanta cea mai mica pana la sursa.
        */
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        for (int i = 1; i <= n; ++i) {
            dist[i] = INF;
            p[i] = NO_PARENT;
        }

        // Vector care retine de cate ori a fost folsit un nod (de cate ori a fost scos din coada).
        vector<int> used(n + 1, 0);

        // Distanta pana la sursa si parintele sunt prin conventie 0
        dist[source] = 0;
        p[source] = 0;

        pq.push({dist[source], source});

        while (!pq.empty()) {
            auto entry  = pq.top();
            pq.pop();

            int node = entry.second;
            int cost = entry.first;

            // cresc numarul de utilizare a nodului
            ++used[node];

            if (used[node] == n) {
                return true;
            }

            // daca nodul extras nu este updated
            if (cost > dist[node]) {
                continue;
            }

            for (auto &it : adj[node]) {
                int neighbour = it.first;
                int edge_cost = it.second;

                if (dist[node] + edge_cost < dist[neighbour]) {
                    // update la distanta
                    dist[neighbour] = dist[node] + edge_cost;
                    
                    // update la printe
                    p[neighbour] = node;

                    // adaug noua valoare pentru distanta pana la vecin in priority queue
                    pq.push({dist[neighbour], neighbour});
                }
            }
        }

        return false;
    }

    vector<int> rebuild_path(int node, vector<int> &p) {
        // daca nu a fost cuprins in parcurgere
        if (p[node] == NO_PARENT) {
            // returneaza vector gol
            return {};
        }

        // calea catre sursa
        vector<int> path;

        // adauga fiecare parinte in vectorul de cale
        for (; node != 0; node = p[node]) {
            path.push_back(node);
        }

        // path-ul e in ordine inversa pentru ca reconstruirea s-a facut pe
        // ierarhia de parinti, deci trebuie inversat
        reverse(path.begin(), path.end());
        
        return path;
    }

    void show_paths(vector<int> &p) {
        // parcurg fiecare nod
        for (int i = 1; i <= n; ++i) {
            // daca nodul actual este sursa
            if (source == i) {
                cout << i << ": nod sursa\n";
                continue;
            }

            // path-ul de la sursa la nodul actual
            vector<int> path = rebuild_path(i, p);

            // daca e vector gol nu s-a parcurs nodul
            if (path.size() == 0) {
                cout << i << ": nu s-a gasit path catre sursa\n";
                continue;
            }

            cout << i << ": ";

            for (auto &it : path) {
                cout << it << " ";
            }

            cout << endl;
        }
    }

    void print_solution() {
        ofstream fout("bellmanford.out");
        if (foundNegativeCicle) {
            fout << "Ciclu negativ!\n";
            return;
        } 

        for (int i = 1; i <= n; ++i) {
            if (i == source) {
                continue;
            }

            fout << dist[i] << " ";
        }

        // decomentez ce e mai jos daca vreau sa afisez si distantele minime

        // cout << endl;

        // show_paths(p);
        fout.close();
    }
};

int main() {
    // assert(freopen("bellmanford.in", "r", stdin) != NULL);
    // assert(freopen("bellmanford.out", "w", stdout) != NULL);

    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}