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

class bellman_ford {
    struct edge {
        int u, v, w;
    };
    vector<edge> edges;
    const int inf = 1e9;
    int n;
public:
    bellman_ford(int n_) { n = n_; edges.clear(); }
    void addEdge(int u, int v, int w) { // adds a bi-directional edge
        edge e;
        e.u = u, e.v = v, e.w = w;
        edges.push_back(e);
        swap(e.u, e.v);
        edges.push_back(e);
    }
    vector<int> sp(int src) {
        vector<int> dis(n, inf);
        dis[src] = 0;
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < edges.size(); j++) {
                dis[edges[j].v] = min(dis[edges[j].v], dis[edges[j].u] + edges[j].w);
            }
        }
        return dis;
    }
};

int main() {
    int n, m; // n = # of nodes, m = # of edges
    cout << "Enter number of nodes: "; cin >> n;
    cout << "Enter number of edges: "; cin >> m;
    cout << "describe all the edges in form:\nnode1 node2 edge_weight" << endl;
    bellman_ford d(n);
    vector<vector<int>> dis(n);
    for(int i = 0; i < m; i++) {
        char a, b; int w;
        cin >> a >> b >> w;
        int u = a - 'A', v = b - 'A';
        d.addEdge(u, v, w);
    }
    for(int src = 0; src < n; src++) dis[src] = d.sp(src);
    cout << "all pair distance using bellman-ford:" << endl;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            char a = i+'A', b = j+'A';
            cout << a << " -> " << b << " : " << dis[i][j] << endl;
        }
    }
}

/*

7 10

A C 2
A E 1
B C 2
B D 13
B E 1
B F 2
C D 8
D G 1
E F 4
F G 2

*/