// Classical Johnson all-pairs shortest paths: BellmanFord computes a
// non-negative price vector that reweights edges, then Dijkstra runs from
// every source on the reweighted graph. Returns null on negative cycle.

class Johnson {
  int[][] allPairs(int[][] w) {
    int n = w.length;
    int INF = 2147483647;
    // Step 1: BellmanFord from auxiliary source s* (0-weight edges to every v).
    // Init dist[i] = 0 (the auxiliary edge); n-1 relaxation passes follow.
    int[] dist = new int[n];
    forall i in [0..n-1] : dist[i] = 0;
    int k = 0;
    while (k < n - 1) {
      boolean changed = false;
      int i = 0;
      while (i < n) {
        int j = 0;
        while (j < n) {
          if (w[i][j] < INF && dist[i] + w[i][j] < dist[j]) {
            dist[j] = dist[i] + w[i][j];
            changed = true;
          };
          j = j + 1;
        };
        i = i + 1;
      };
      if (!changed) {
        k = n;
      } else {
        k = k + 1;
      }
    };
    // One more pass: any further relaxation means negative cycle.
    int i = 0;
    while (i < n) {
      int j = 0;
      while (j < n) {
        if (w[i][j] < INF && dist[i] + w[i][j] < dist[j]) {
          return null;
        };
        j = j + 1;
      };
      i = i + 1;
    };
    // Step 2: price[v] = -dist[v].
    int[] price = new int[n];
    forall v in [0..n-1] : price[v] = 0 - dist[v];
    // Step 3: reweight every edge.
    int[][] wPrime = new int[n][n];
    i = 0;
    while (i < n) {
      int j = 0;
      while (j < n) {
        if (w[i][j] < INF) {
          wPrime[i][j] = w[i][j] + price[j] - price[i];
        } else {
          wPrime[i][j] = INF;
        };
        j = j + 1;
      };
      i = i + 1;
    };
    // Step 4: Dijkstra from every source; undo the reweighting.
    int[][] D = new int[n][n];
    int u = 0;
    while (u < n) {
      int[] distPrime = dijkstra(wPrime, u, n);
      int v = 0;
      while (v < n) {
        if (distPrime[v] < INF) {
          D[u][v] = distPrime[v] + price[u] - price[v];
        } else {
          D[u][v] = INF;
        };
        v = v + 1;
      };
      u = u + 1;
    };
    return D;
  }

  int[] dijkstra(int[][] w, int s, int n) {
    int INF = 2147483647;
    int[] dist = new int[n];
    boolean[] fixed = new boolean[n];
    forall i in [0..n-1] : dist[i] = INF;
    dist[s] = 0;
    int count = 0;
    while (count < n) {
      int j = 0 - 1;
      int best = INF;
      int k = 0;
      while (k < n) {
        if (!fixed[k] && dist[k] < best) {
          j = k;
          best = dist[k];
        };
        k = k + 1;
      };
      if (j == 0 - 1) {
        return dist;
      };
      fixed[j] = true;
      count = count + 1;
      k = 0;
      while (k < n) {
        if (!fixed[k] && w[j][k] < INF && dist[j] + w[j][k] < dist[k]) {
          dist[k] = dist[j] + w[j][k];
        };
        k = k + 1;
      }
    };
    return dist;
  }
}