#include <iostream>
#include <vector>
#include <limits>

using namespace std;

#define INF (numeric_limits<int>::max())

typedef int                             Node;
typedef vector<vector<pair<Node, int>>> List;

void relax(vector<int>& distance, vector<int>& pi, 
           int u, int v, int w)
{
    if (distance[v] > distance[u] + w) {
        distance[v] = distance[u] + w;
        pi[v] = u;
    }
}

void init(vector<int>& distance, vector<int>& pi, int n, int s)
{
    distance.resize(n, INF);
    distance[s] = 0;
    pi.resize(n, -1);
}

bool ballman_ford(List& neighbours, vector<int>& distance,
                  vector<int>& pi, int s)
{
    const int n = neighbours.size();
    init(distance, pi, n, s);
    for (int i = 0; i < n - 1; i++) {
        for (Node u = 0; u < n; u++) {
            for (auto [v, w] : neighbours[u]) {
                relax(distance, pi, u, v, w);
            }
        }
    }

    for (Node u = 0; u < n; u++) {
        for (auto [v, w] : neighbours[u]) {
            if (distance[v] > distance[u] + w) {
                return false;
            }
        }
    }

    return true;
}

int main(int argc, const char *argv[])
{
    List neighbours = {
        { {1, 6}, {3, 7} },
        { {2, 5}, {3, 8}, {4, -4} },
        { {1, -2} },
        { {2, -3}, {4, 9} },
        { {0, 8}, {2, 7} }
    };

    vector<int> distance;
    vector<int> pi;
    if (ballman_ford(neighbours, distance, pi, 0)) {
        cout << "Ne postoji ciklus negativne tezine dostizan od s!" << endl;
        for (Node u = 0; u < distance.size(); u++) {
            cout << u << ": " << distance[u] << endl;
        }
    } else {
        cout << "Postoji ciklus negativne tezine dostizan od s!" << endl;
    }
    
    return 0;
}