// Classical Prim MST: O(n²) linear-scan version using a weight matrix.

class Prim {
  int[] mst(int[][] w) {
    int n = w.length;
    int[] d = new int[n];
    int[] parent = new int[n];
    boolean[] fixed = new boolean[n];
    forall i in [0..n-1] : { d[i] = 2147483647; parent[i] = -1; };
    d[0] = 0;
    int count = 0;
    while (count < n) {
      // Linear scan for the unfixed vertex with min d.
      int v = -1;
      int best = 2147483647;
      int k = 0;
      while (k < n) {
        if (!fixed[k] && d[k] < best) {
          v = k;
          best = d[k];
        };
        k = k + 1;
      };
      if (v == -1) {
        return parent;
      };
      fixed[v] = true;
      count = count + 1;
      // Relax edges out of v: update d to the lighter direct edge.
      k = 0;
      while (k < n) {
        if (!fixed[k] && w[v][k] != 2147483647 && w[v][k] < d[k]) {
          d[k] = w[v][k];
          parent[k] = v;
        };
        k = k + 1;
      }
    };
    return parent;
  }
}