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

class graf {

    const int INF= (1<<30);

    struct muchie {
        int x, y, cost;
    };

    struct comp
    {
        inline bool operator() (const muchie& a, const muchie& b)
        {
            return a.cost < b.cost;
        }
    };

    vector < bool > vis, visInversate;
    vector < vector < int > > muchii, muchiiInversate, solCtc;
    vector < int > multime, nrElemente;
    vector < muchie > apm;

    void dfs(int node) {

        vis[node] = true;

        for (int index = 0; index < muchii[node].size(); ++index) {
            int nextNode = muchii[node][index];

            if (!vis[nextNode]) {
                dfs(nextNode);
            }
        }

    }

    void dfsInversate(int node, int nrSol) {

        visInversate[node] = true;
        solCtc[nrSol].push_back(node);

        for (int index = 0; index < muchiiInversate[node].size(); ++index) {
            int nextNode = muchiiInversate[node][index];

            if (!visInversate[nextNode]) {
                dfsInversate(nextNode, nrSol);
            }
        }

    }

    int numarComponenteConexe() {

        int counter = 0;
        int n = muchii.size() - 1;

        vis.resize(n + 1, false);

        for (int node = 1; node <= n; ++node)
            if (!vis[node]) {
                ++counter;
                dfs(node);
            }
        return counter;
    }

    vector < int > bfs(int sursa) {
        int n = muchii.size() - 1;

        queue < int > coadaBfs;
        vector < int > listaBfs;
        listaBfs.resize(n + 1, -1);

        listaBfs[sursa] = 0;
        coadaBfs.push(sursa);

        while (!coadaBfs.empty()) {
            int nod = coadaBfs.front();
            coadaBfs.pop();

            for (int i = 0; i < muchii[nod].size(); ++i)
                if (listaBfs[muchii[nod][i]] == -1) {
                    listaBfs[muchii[nod][i]] = listaBfs[nod] + 1;
                    coadaBfs.push(muchii[nod][i]);
                }
        }

        return listaBfs;
    }

    void dfsSortareTopologica(int nod, stack < int > &topo) {

        vis[nod] = 1;

        for (int i = 0; i < muchii[nod].size(); ++i)
            if (vis[muchii[nod][i]] == 0)
                dfsSortareTopologica(muchii[nod][i], topo);

        topo.push(nod);
    }

    pair < int, vector < vector < int > > > ctc(int n) {

        int nrSol = 0;
        stack < int > topo;

        vis.resize(n + 1, false);
        visInversate.resize(n + 1, false);
        solCtc.resize(n + 1);

        for (int i = 1; i<= n; ++i)
            if (vis[i] == 0)
                dfsSortareTopologica(i, topo);

        while(!topo.empty()) {

            int nod = topo.top();
            topo.pop();

            if (visInversate[nod] == 0) {
                nrSol++;
                dfsInversate(nod, nrSol);
            }

        }

        return make_pair(nrSol, solCtc);
    }

    int cauta(int val) {

        int radacina = val, aux;

        while (multime[radacina] != radacina)
            radacina = multime[radacina];

        while (multime[val] != radacina) {

            aux = multime[val];
            multime[val] = radacina;
            val = aux;
        }

        return radacina;
    }

    void uneste(int a, int b) {

        int radacinaA, radacinaB;

        radacinaA = cauta(a);
        radacinaB = cauta(b);

        if (nrElemente[radacinaA] < nrElemente[radacinaB]) {

            nrElemente[radacinaB] += nrElemente[radacinaA];
            multime[radacinaA] = radacinaB;
        }
        else {

            nrElemente[radacinaA] += nrElemente[radacinaB];
            multime[radacinaB] = radacinaA;
        }

    }

    vector < muchie > apmSol(int m) {

        vector < muchie > solApm;

        sort(apm.begin(), apm.end() - 1, comp());

        for (int i = 0; i < m; ++i) {

            int a = apm[i].x;
            int b = apm[i].y;

            int radacinaA = cauta(a);
            int radacinaB = cauta(b);

            if (radacinaA != radacinaB) {

                uneste(a, b);
                muchie aux;
                aux.x = a;
                aux.y = b;
                aux.cost = apm[i].cost;
                solApm.push_back(aux);
            }
        }
        return solApm;
    }

    bool havelHakimi(vector < int > grade) {

        int n = grade.size();

        while (1) {

            sort(grade.begin(), grade.end(), greater < int >());

            if (grade[0] == 0) return true;

            int grad = grade[0];
            grade.erase(grade.begin());


            if (grad > grade.size()) return false;

            for (int i = 0; i < grad; ++i) {

                grade[i]--;

                if (grade[i] < 0) return false;
            }
        }
    }

    vector < vector < int > > royFloyd(vector < vector < int > > matrice, int n) {

        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    if ( (1LL * matrice[i][k] + 1LL * matrice[k][j]) < matrice[i][j] )
                        matrice[i][j] = matrice[i][k] + matrice[k][j];

        return matrice;
    }

    vector < int > dijkstra(vector < vector < int > > costuri, int n) {

        vector < int > dist;
        priority_queue < pair < int, int > , vector < pair < int, int > > , greater < pair < int, int > > > S;

        dist.resize(n + 1, INF);
        vis.resize(n + 1, false);

        dist[1] = 0;
        S.push({0, 1});

        while (!S.empty()) {

            int nod = S.top().second;
            int cost = S.top().first;
            S.pop();

            if (vis[nod] == true) continue;
            else vis[nod] = true;

            for (int i = 0; i < muchii[nod].size(); ++i) {

                int urmNod = muchii[nod][i];

                if (dist[urmNod] > costuri[nod][i] + cost) {

                    dist[urmNod] = costuri[nod][i] + cost;
                    S.push({dist[urmNod], urmNod});
                }
            }
        }

        return dist;
    }

    vector < int > bellmanFord(vector < vector < int > > costuri, int n, int& ciclu) {

        vector < int > dist, numar;

        dist.resize(n + 1, INF);
        vis.resize(n + 1, false);
        numar.resize(n + 1, 0);
        queue < int > coada;

        dist[1] = 0;
        coada.push(1);
        vis[1] = true;
        ciclu = 0;

        while (!coada.empty()) {

            int nodSursa = coada.front();
            coada.pop();
            vis[nodSursa] = false;
            numar[nodSursa]++;

            if (numar[nodSursa] == n) {

                ciclu = 1;
                return dist;
            }

            for (int i = 0; i < muchii[nodSursa].size(); ++i) {

                int nodDest = muchii[nodSursa][i];
                int cost = costuri[nodSursa][i];

                if (dist[nodSursa] + cost < dist[nodDest]) {

                    dist[nodDest] = dist[nodSursa] + cost;

                    if (vis[nodDest] == 0) {

                        vis[nodDest] = true;
                        coada.push(nodDest);

                    }
                }
            }
        }

        return dist;
    }

public:

    void dfsInfoarena() {

        ifstream in("dfs.in");
        ofstream out("dfs.out");

        int n, m, x, y;

        in >> n >> m;

        muchii.resize(n + 1);

        for (int index = 1; index <= m; ++index) {
            in >> x >> y;

            muchii[x].push_back(y);
            muchii[y].push_back(x);
        }

        out << numarComponenteConexe();
    }

    void bfsInfoarena() {

        ifstream in("bfs.in");
        ofstream out("bfs.out");

        int n, m, nod, x, y;

        in >> n >> m >> nod;

        muchii.resize(n + 1);

        for (int index = 1; index <= m; ++index) {
            in >> x >> y;

            muchii[x].push_back(y);
        }

        vector < int > raspuns = bfs(nod);

        for (int i = 1; i <= n; ++i)
            out << raspuns[i] << " ";
    }

    void sortareTopologicaInfoarena() {

        ifstream in("sortaret.in");
        ofstream out("sortaret.out");

        int n, m, x, y;
        stack < int > topo;

        in >> n >> m;

        vis.resize(n + 1, false);
        muchii.resize(n + 1);

        for (int index = 1; index <= m; ++index) {
            in >> x >> y;

            muchii[x].push_back(y);
        }

        for (int i = 1; i<= n; ++i)
            if (vis[i] == 0)
                dfsSortareTopologica(i, topo);

        while (!topo.empty()) {
            int val = topo.top();
            topo.pop();

            out << val << " ";
        }
    }

    void ctcInfoarena() {

        ifstream in("ctc.in");
        ofstream out("ctc.out");

        int n, m, x, y;

        in >> n >> m;

        muchii.resize(n + 1);
        muchiiInversate.resize(n + 1);

        for (int i = 1; i <= m; ++i) {

            in >> x >> y;

            muchii[x].push_back(y);
            muchiiInversate[y].push_back(x);
        }

        pair < int, vector < vector < int > > > sol = ctc(n);

        out << sol.first << "\n";

        for (int i = 1; i <= sol.first; ++i) {

            int m = sol.second[i].size();

            for (int j = 0; j < m; ++j)
                out << sol.second[i][j] << " ";

            out << "\n";
        }
    }

    void disjointInfoarena() {

        ifstream in("disjoint.in");
        ofstream out("disjoint.out");

        int n, m, op, x, y;

        in >> n >> m;

        multime.resize(n + 1);
        nrElemente.resize(n + 1, 1);

        for (int i = 1; i <= n; ++i) multime[i] = i;

        for (int i = 1; i <= m; ++i) {

            in >> op >> x >> y;

            if (op == 1) uneste(x, y);
            else {

                int radacinaX = cauta(x);
                int radacinaY = cauta(y);

                if (radacinaX == radacinaY) out << "DA" << "\n";
                else out << "NU" << "\n";
            }

        }

    }

    void apmInfoarena() {

        ifstream in("apm.in");
        ofstream out("apm.out");

        int n, m, suma = 0;

        vector < muchie > solApm;

        in >> n >> m;

        multime.resize(n + 1);
        nrElemente.resize(n + 1, 1);
        apm.resize(m + 1);
        solApm.resize(m + 1);

        for(int i = 1; i <= n; ++i)
            multime[i] = i;


        for (int i = 0; i < m; ++i)
            in >> apm[i].x >> apm[i].y >> apm[i].cost;

        solApm = apmSol(m);

        for (int i = 0; i < solApm.size(); ++i)
            suma += solApm[i].cost;

        out << suma << "\n" << solApm.size() << "\n";

        for (int i = 0; i < solApm.size(); ++i)
            out << solApm[i].x << " " << solApm[i].y << "\n";
    }

    void solveHavelHakimi() {

        ifstream in("havelhakimi.in");
        ofstream out("havelhakimi.out");

        int n;
        vector < int > hakimi;

        in >> n;

        hakimi.resize(n + 1);

        for (int i = 0; i < n; ++i)
            in >> hakimi[i];

        bool raspuns = havelHakimi(hakimi);

        if (raspuns) out << "DA";
        else out << "NU";
    }

    void royFloydInfoarena() {

        ifstream in("royfloyd.in");
        ofstream out("royfloyd.out");

        int n, x;
        vector < vector < int > > matrice;

        in >> n;

        matrice.resize(n + 1);

        for (int i = 1; i <= n; ++i)
            matrice[i].push_back(0);

        for (int i = 1; i <= n; ++i) {

            for(int j = 1; j <= n; ++j)
                matrice[i].push_back(INF);

            matrice[i][i] = 0;
        }

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {

                in >> x;
                if (x) matrice[i][j] = x;
            }

        matrice = royFloyd(matrice, n);

        for (int i = 1; i <= n; ++i) {

            for (int j = 1; j <= n; ++j)
                out << matrice[i][j] << " ";
            out << "\n";
        }
    }

    void dijkstraInfoarena() {

        ifstream in("dijkstra.in");
        ofstream out("dijkstra.out");

        int n, m, x, y, cost;

        vector < vector < int > > costuri;

        in >> n >> m;

        muchii.resize(n + 1);
        costuri.resize(n + 1);

        for (int i = 1; i <= m; ++i) {

            in >> x >> y >> cost;

            muchii[x].push_back(y);
            costuri[x].push_back(cost);
        }

        vector < int > dist = dijkstra(costuri, n);

        for (int i = 2; i <= n; ++i)
            if (dist[i] == INF) out << 0 << " ";
            else out << dist[i] << " ";
    }

    void bellmanFordInfoarena() {

        ifstream in("bellmanford.in");
        ofstream out("bellmanford.out");

        int n, m, x, y, cost, ciclu;
        vector < vector < int > > costuri;

        in >> n >> m;

        muchii.resize(n + 1);
        costuri.resize(n + 1);

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

            muchii[x].push_back(y);
            costuri[x].push_back(cost);
        }
        vector < int > sol = bellmanFord(costuri, n, ciclu);

        if (ciclu == 1) {
            out << "Ciclu negativ!";
            return;
        }

        for(int i = 2; i <= n; ++i)
            out << sol[i] << " ";

    }

};

int main()
{
    graf g;

    g.bellmanFordInfoarena();

    return 0;
}