All pairs (Floyd–Warshall) (Shortest Paths (Weighted) Sub-pattern)

// Floyd-Warshall: shortest path between every pair. After the k-loop finishes for k,
// d[i][j] is the best path whose middle nodes are all among 0..k.
vector<vector<long long>> allPairs(int n, const vector<vector<int>>& edges) {   // undirected {u, v, w}
    const long long INF = LLONG_MAX / 4;          // /4 so INF + INF can't overflow
    vector<vector<long long>> d(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (auto& e : edges) {
        d[e[0]][e[1]] = min<long long>(d[e[0]][e[1]], e[2]);
        d[e[1]][e[0]] = min<long long>(d[e[1]][e[0]], e[2]);
    }
    for (int k = 0; k < n; k++)                   // k MUST be the outer loop
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
    return d;
}