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

class dijkstra {
    int n; vector<vector<pair<int,int>>> g;
public:
    dijkstra(int n_) { n = n_; g.assign(n, {}); }
    void addEdge(int u, int v, int w) { // adds a bi-directional edge
        g[u].push_back({v, w}); g[v].push_back({u, w});
    }
    vector<int> sp(int src) {
        vector<int> dis(n, -1);
        dis[src] = 0; priority_queue<pair<int,int>> pq; pq.push({0, src});
        while(pq.size() > 0) {
            auto t = pq.top(); pq.pop();
            int u = t.second;
            if(dis[u] != -t.first) continue;
            for(auto nxt : g[u]) {
                int v = nxt.first, w = nxt.second;
                if(dis[v] == -1 or dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.push({-dis[v], v});
                }
            }
        }
        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;
    dijkstra 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 dijkstra:" << 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

*/