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

struct Edge
{
    int src, dest, weight;
};

struct Graph
{
    int V, E;

    struct Edge* edge;
};

struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[E];
    return graph;
}

void printArr(int dist[], int n, int src)
{
    cout<<endl;
    cout<<"__________________________________"<<endl;
    cout<<"Routing Table for "<<src<<endl;
    cout<<"__________________________________"<<endl;;
    for (int i = 0; i < n; ++i)
    {
        if(i == src)
            continue;
        cout<<"Distance to router "<<i<<" --> "<<dist[i]<<endl;
    }
    cout<<"__________________________________"<<endl;;
    cout<<endl;
}

void BellmanFord(struct Graph* graph, int src)
{
    int V = graph->V;
    int E = graph->E;
    int dist[V];

    for (int i = 0; i < V; i++)
        dist[i]   = INT_MAX;
    dist[src] = 0;

    for (int i = 1; i <= V-1; i++)
    {
        for (int j = 0; j < E; j++)
        {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    for (int i = 0; i < E; i++)
    {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
            printf("Graph contains negative weight cycle");
    }

    printArr(dist, V, src);

    return;
}

int main()
{
    int V;
    int E;
    cout<<"Enter number of vertices ";
    cin>>V;
    cout<<"Enter number of edges ";
    cin>>E;
    struct Graph* graph = createGraph(V, 2*E);

    for(int i = 0;i<2*E;i+=2)
    {
        cout<<"Enter source, destination and weight"<<endl;
        int src, dest, weight;
        cin>>src>>dest>>weight;
        graph->edge[i].src = src;
        graph->edge[i].dest = dest;
        graph->edge[i].weight = weight;
        graph->edge[i+1].src = dest;
        graph->edge[i+1].dest = src;
        graph->edge[i+1].weight = weight;

    }
    for(int i = 0;i<V;i++)
        BellmanFord(graph, i);

    return 0;
}