Distances between every pair of nodes

def all_pairs(n, edges):
    INF = float('inf')
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)          # keep the lighter of parallel edges
    for k in range(n):                     # allow k as an intermediate node
        dk = d[k]
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(n):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    return [[-1 if x == INF else x for x in row] for row in d]

#include <algorithm>
#include <climits>
#include <vector>

std::vector<std::vector<long long>> solve(int n, const std::vector<std::vector<int>>& edges) {
    const long long INF = LLONG_MAX / 4;
    std::vector<std::vector<long long>> d(n, std::vector<long long>(n, INF));
    for (int i = 0; i < n; ++i) d[i][i] = 0;
    for (const auto& e : edges) d[e[0]][e[1]] = std::min<long long>(d[e[0]][e[1]], e[2]);
    for (int k = 0; k < n; ++k)                       // allow k as an intermediate
        for (int i = 0; i < n; ++i) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; ++j)
                if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        }
    for (auto& row : d)
        for (auto& x : row)
            if (x == INF) x = -1;
    return d;
}

class Solution {
    public int[][] allPairs(int n, int[][] edges) {
        final long INF = Long.MAX_VALUE / 4;
        long[][] d = new long[n][n];
        for (int i = 0; i < n; i++) {
            java.util.Arrays.fill(d[i], INF);
            d[i][i] = 0;
        }
        for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
        for (int k = 0; k < n; k++)                    // allow k as an intermediate
            for (int i = 0; i < n; i++) {
                if (d[i][k] == INF) continue;
                for (int j = 0; j < n; j++)
                    if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
            }
        int[][] out = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) out[i][j] = d[i][j] == INF ? -1 : (int) d[i][j];
        return out;
    }
}

function allPairs(n, edges) {
  const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);   // lighter parallel edge
  for (let k = 0; k < n; k++) {                                   // allow k as an intermediate
    for (let i = 0; i < n; i++) {
      if (d[i][k] === Infinity) continue;
      for (let 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.map(row => row.map(x => (x === Infinity ? -1 : x)));
}

fn solve(n: i64, edges: &[[i64; 3]]) -> Vec<Vec<i64>> {
    let n = n as usize;
    let mut d: Vec<Vec<Option<i64>>> = (0..n).map(|i| (0..n).map(|j| if i == j { Some(0) } else { None }).collect()).collect();
    for e in edges {
        let (u, v, w) = (e[0] as usize, e[1] as usize, e[2]);
        d[u][v] = Some(d[u][v].map_or(w, |x| x.min(w)));   // lighter parallel edge
    }
    for k in 0..n {                                       // allow k as an intermediate
        for i in 0..n {
            let Some(dik) = d[i][k] else { continue };
            for j in 0..n {
                if let Some(dkj) = d[k][j] {
                    if d[i][j].map_or(true, |x| dik + dkj < x) {
                        d[i][j] = Some(dik + dkj);
                    }
                }
            }
        }
    }
    d.into_iter().map(|row| row.into_iter().map(|x| x.unwrap_or(-1)).collect()).collect()
}

import Data.List (foldl')
import qualified Data.Map.Strict as M

solve :: Int -> [[Int]] -> [[Int]]
solve n edges = [[maybe (-1) id (M.lookup (i, j) final) | j <- [0 .. n - 1]] | i <- [0 .. n - 1]]
  where
    -- a map holds only the finite distances; a missing key is infinity
    start = M.fromListWith min ([((i, i), 0) | i <- [0 .. n - 1]] ++ [((u, v), w) | [u, v, w] <- edges])
    final = foldl' through start [0 .. n - 1]
    through d k = M.fromList
      [ ((i, j), best)
      | i <- [0 .. n - 1], j <- [0 .. n - 1]
      , let viaK = (+) <$> M.lookup (i, k) d <*> M.lookup (k, j) d
      , Just best <- [minMaybe (M.lookup (i, j) d) viaK] ]
    minMaybe (Just a) (Just b) = Just (min a b)
    minMaybe a Nothing = a
    minMaybe Nothing b = b