#include <iostream>
#include <bits/stdc++.h>

using namespace std;

class graph
{
    // bitul 1 orientat sau neorientat, bitul 2 cost muchie
    enum input {orientat = 1, neorientat = 2, cu_cost = 4, fillLat = 8};
    struct muchie
    {
        int from, to, cost;
        muchie(int _from, int _to, int _cost = 1):
            from(_from), to(_to), cost(_cost)
            {

            }
    };
    int n,m;
    int* extraArgs = nullptr;

    vector<int>* la = nullptr;
    vector<int>* lat = nullptr;
    vector<pair<int,int>>* lac = nullptr;

    int* used = nullptr;
    int* parents = nullptr;
    int* dist = nullptr;
    int* ids = nullptr;
    int id = 0;
    int* lowLink = nullptr;

    vector<int> topo;

    ifstream f;
    ofstream g;
public:
    void readData(string nume_fisier, input _tip_graf, vector<pair<int**, int>> initVecs = vector<pair<int**,int>>(), int _extra_args_count = 0);
    //////////////////////////////////////////////////////////////////////////////////
    void bfs();
    //////////////////////////////////////////////////////////////////////////////////
    void dfs();
    void dfsTopo(int from);
    //////////////////////////////////////////////////////////////////////////////////
    void ctc();
    void dfsCtc(int nod, vector<vector<int>>& cc);
    //////////////////////////////////////////////////////////////////////////////////
    void sortaret();
    //////////////////////////////////////////////////////////////////////////////////
    void critice();
    void dfsCritice(int from, int parent, vector<pair<int,int>>& mcrit);
    //////////////////////////////////////////////////////////////////////////////////
    void biconex();
    void dfsBiconexe(int from, stack<pair<int,int>>& st, vector<vector<int>>& cb);
    //////////////////////////////////////////////////////////////////////////////////
    void apm();
    pair<int,int> getParentAndHeight(int x);
    //////////////////////////////////////////////////////////////////////////////////
    void disjoint();
    //////////////////////////////////////////////////////////////////////////////////
    void dijkstra();
    //////////////////////////////////////////////////////////////////////////////////
    void bellmanford();
};

void graph::readData (string nume_fisier, input _tip_graf, vector<pair<int**, int>> initVecs, int _extra_args_count)
{
    f.open(nume_fisier);

    f >> n >> m;

    for (auto& per: initVecs)
    {
        int** p = per.first;
        int val = per.second;
        *p = new int[n+1];
        for (int i = 1; i <= n; i++)
            (*p)[i] = val;
    }

    if (_extra_args_count)
    {
        extraArgs = new int[_extra_args_count];
        for (int i = 0; i < _extra_args_count; i++)
            f >> extraArgs[i];
    }
    int x,y,c;

    if (_tip_graf & input::orientat)
    {
        if (_tip_graf & input::cu_cost)
        {
            lac = new vector<pair<int,int>>[n+1];
            for (int i = 1; i <= m; i++)
            {
                f >> x >> y >> c;
                lac[x].push_back({y,c});
            }
        }
        else
        {
            if (_tip_graf & input::fillLat)
            {
                la = new vector<int>[n+1];
                lat = new vector<int>[n+1];
                for (int i = 1; i <= m; i++)
                {
                    f >> x >> y;
                    // cout << x << ' ' << y << '\n';
                    la[x].push_back(y);
                    lat[y].push_back(x);
                }
            }
            else
            {
                la = new vector<int>[n+1];
                for (int i = 1; i <= m; i++)
                {
                    f >> x >> y;
                    la[x].push_back(y);
                }
            }
        }
    }
    else if (_tip_graf & input::neorientat)
    {
        if (_tip_graf & input::cu_cost)
        {
            lac = new vector<pair<int,int>>[n+1];
            for (int i = 1; i <= m; i++)
            {
                f >> x >> y >> c;
                lac[x].push_back({y,c});
                lac[y].push_back({x,c});
            }
        }
        else
        {
            la = new vector<int>[n+1];
            for (int i = 1; i <= m; i++)
            {
                f >> x >> y;
                la[x].push_back(y);
                la[y].push_back(x);
            }
        }
    }

    f.close();
}

void graph::bfs()
{
    ofstream g("bfs.out");
    readData("bfs.in", input::orientat, {{&dist, -1}}, 1);

    int start = extraArgs[0];

    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (q.size())
    {
        for (auto to: la[q.front()])
        {
            if (dist[to] == -1)
            {
                q.push(to);
                dist[to] = dist[q.front()] + 1;
            }
        }
        q.pop();
    }

    for (int i = 1; i <= n; i++)
        g << dist[i] << ' ';

    delete[] la;
    delete[] extraArgs;
    delete[] dist;
}

void graph::dfsTopo(int from)
{
    dist[from] = 1;
    for (auto to: la[from])
    {
        if (!dist[to])
            dfsTopo(to);
    }
    topo.push_back(from);
}

void graph::dfs()
{
    ofstream g("dfs.out");
    readData("dfs.in", input::neorientat, {{&dist, 0}});

    int cc = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!dist[i])
        {
            dfsTopo(i);
            cc++;
        }
    }

    g << cc;

    delete[] la;
    delete[] dist;
}

void graph::dfsCtc(int nod, vector<vector<int>>& cc)
{
    dist[nod] = 1;
    cc[cc.size() - 1].push_back(nod);
    for (auto to: lat[nod])
    {
        if (!dist[to])
            dfsCtc(to, cc);
    }
}

void graph::ctc()
{
    ofstream g("ctc.out");
    readData("ctc.in", (input)(input::orientat | input::fillLat), {{&dist, 0}});

    for (int i = 1; i <= n; i++)
    {
        if (!dist[i])
            dfsTopo(i);
    }
    reverse(topo.begin(), topo.end());

    memset(dist, 0, sizeof(int) * (n+1));
    vector<vector<int>> cc;
    for (auto nod: topo)
    {
        if (!dist[nod])
        {
            cc.push_back(vector<int>());
            dfsCtc(nod, cc);
        }
    }

    g << cc.size() << '\n';
    for (auto& row: cc)
    {
        for (auto el: row)
            g << el << ' ';
        g << '\n';
    }

    delete[] dist;
    delete[] la;
    delete[] lat;
}

void graph::sortaret()
{
    ofstream g("sortaret.out");
    readData("sortaret.in", (input)(input::orientat), {{&dist, 0}});

    for (int i = 1; i <= n; i++)
    {
        if (!dist[i])
            dfsTopo(i);
    }
    reverse(topo.begin(), topo.end());

    for (auto el: topo)
        g << el << ' ';

    delete[] dist;
    delete[] la;
}

void graph::dfsCritice(int from, int parent, vector<pair<int,int>>& mcrit)
{
    lowLink[from] = id;
    ids[from] = id;
    id ++;
    for (auto to: la[from])
    {
        if (ids[to] == -1)
        {
            dfsCritice(to, from, mcrit);
            lowLink[from] = min(lowLink[from], lowLink[to]);
        }
        else if (to != parent)
            lowLink[from] = min(lowLink[from], ids[to]);
    }
    if (lowLink[from] == ids[from] && parent != 0)
        mcrit.push_back({from, parent});
}

void graph::critice()
{
    ofstream g("critice.out");
    readData("critice.in", (input)(input::neorientat), {{&ids, -1}, {&lowLink, 0}});

    vector<pair<int, int>> mcrit;
    for (int i = 1; i <= n; i++)
    {
        if (ids[i] == -1)
        {
            dfsCritice(i, 0, mcrit);
        }
    }

    for (auto& per: mcrit)
        g << per.first << ' ' << per.second << '\n';

    delete[] la;
    delete[] ids;
    delete[] lowLink;
}

void graph::dfsBiconexe(int from, stack<pair<int,int>>& st, vector<vector<int>>& cb)
{
    lowLink[from] = ids[from] = id++;

    for (auto to: la[from])
    {
        if (ids[to] != -1)
            lowLink[from] = min(lowLink[from], ids[to]);
        else
        {
            st.push({from, to});
            dfsBiconexe(to, st, cb);

            lowLink[from] = min(lowLink[from], lowLink[to]);

            if (lowLink[to] >= ids[from])
            {
                vector<int> comp;
                while (st.top().first != from)
                {
                    comp.push_back(st.top().second);
                    st.pop();
                }
                comp.push_back(st.top().first);
                comp.push_back(st.top().second);
                st.pop();
                cb.push_back(comp);
            }
        }
    }
}

void graph::biconex()
{
    ofstream g("biconex.out");
    readData("biconex.in", (input)(input::neorientat), {{&ids, -1}, {&lowLink, 0}});

    vector<vector<int>> cb;
    stack<pair<int,int>> st;
    for (int i = 1; i <= n; i++)
    {
        if (ids[i] == -1)
            dfsBiconexe(i, st, cb);
    }

    g << cb.size() << '\n';
    for (auto& row: cb)
    {
        for (auto el: row)
            g << el << ' ';
        g << '\n';
    }

    delete[] ids;
    delete[] lowLink;
    delete[] la;
}

pair<int,int> graph::getParentAndHeight(int x)
{
    vector<int> met;
    int h = 0;
    while (parents[x] != 0)
    {
        h++;
        met.push_back(x);
        x = parents[x];
    }
    for (auto el: met)
        parents[el] = x;
    return {x, h};
}

void graph::apm()
{
    ofstream g("apm.out");
    readData("apm.in", (input)(input::orientat | input::cu_cost), {{&parents, 0}});

    vector<muchie> muchii;
    for (int i = 1; i <= n; i++)
    {
        for (auto per: lac[i])
            muchii.push_back({i, per.first, per.second});
    }

    sort(muchii.begin(), muchii.end(), [](muchie& m1, muchie& m2){ return (m1.cost < m2.cost);});

    vector<muchie> sol;
    int s = 0;
    for (auto& m: muchii)
    {
        auto [p1, h1] = getParentAndHeight(m.from);
        auto [p2, h2] = getParentAndHeight(m.to);

        if (p1 == p2)
            continue;
        if (h1 > h2)
        {
            parents[p1] = p2;
        }
        else
        {
            parents[p2] = p1;
        }
        sol.push_back(m);
        s += m.cost;
    }

    g << s << '\n';
    g << sol.size() << '\n';
    for (auto& m: sol)
        g << m.from << ' ' << m.to << '\n';

    delete[] parents;
    delete[] lac;
}

void graph::disjoint()
{
    ifstream f("disjoint.in");
    ofstream g("disjoint.out");
    f >> n >> m;
    parents = new int[n+1];
    memset(parents, 0, sizeof(int)*(n+1));

    for (int i = 1; i <= m; i++)
    {
        int op, from, to;
        f >> op >> from >> to;
        auto [p1, h1] = getParentAndHeight(from);
        auto [p2, h2] = getParentAndHeight(to);
        if (op == 1)
        {
            if (h1 > h2)
                parents[p2] = p1;
            else
                parents[p1] = p2;
        }
        else
        {
            if (p1 == p2)
                g << "DA\n";
            else
                g << "NU\n";
        }
    }

    delete[] parents;
}

void graph::dijkstra()
{
    const int max_dist = 1111111111;
    ofstream g("dijkstra.out");
    readData("dijkstra.in", (input)(input::orientat | input::cu_cost), {{&dist, max_dist}});

    queue<int> q; // cost negativ si nod
    q.push(1);
    dist[1] = 0;

    while (q.size())
    {
        int top = q.front();
        for (auto& per: lac[top])
        {
            if (dist[per.first] > dist[top] + per.second)
            {
                dist[per.first] = dist[top] + per.second;
                q.push(per.first);
            }
        }
        q.pop();
    }

    for (int i = 2; i <= n; i++)
    {
        if (dist[i] == max_dist)
        {
            dist[i] = 0;
        }
        g << dist[i] << ' ';
    }

    delete[] dist;
    delete[] lac;
}

void graph::bellmanford()
{
    const int max_dist = 1111111111;
    ofstream g("bellmanford.out");
    readData("bellmanford.in", (input)(input::orientat | input::cu_cost), {{&dist, max_dist}, {&used, 0}});

    vector<int> to_check_now;
    to_check_now.push_back(1);
    dist[1] = 0;
    for (int k = 1; k <= n && to_check_now.size(); k++)
    {
        vector<int> to_check_next;
        for (int i = 1; i <= n; i++)
            used[i] = 0;

        for (auto el: to_check_now)
        {
            for (auto& m: lac[el])
            {
                if (dist[m.first] > dist[el] + m.second)
                {
                    dist[m.first] = dist[el] + m.second;
                    if (!used[m.first])
                    {
                        used[m.first] = 1;
                        to_check_next.push_back(m.first);
                    }
                }
            }
        }
        to_check_next.swap(to_check_now);
    }
    for (auto el: to_check_now)
            for (auto& m: lac[el])
                if (dist[m.first] > dist[el] + m.second)
                {
                    g << "Ciclu negativ!";
                    return;
                }

    for (int i = 2; i <= n; i++)
    {
        if (max_dist == dist[i])
            dist[i] = 0;
        g << dist[i] << ' ';
    }

    delete[] dist;
    delete[] lac;
    delete[] used;
}

int main()
{
    graph g;
    g.bellmanford();

    return 0;
}