class UnionFind {
  parent: number[];
  rank: number[];

  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = Array(size).fill(0);
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x: number, y: number) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX] += 1;
      }
    }
  }
}

function kruskal(n: number, edges: [number, number, number][]): number {
  edges.sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(n);
  let totalWeight = 0;
  let edgeCount = 0;

  for (const [u, v, weight] of edges) {
    if (uf.find(u) !== uf.find(v)) {
      uf.union(u, v);
      totalWeight += weight;
      edgeCount += 1;
      if (edgeCount === n - 1) break;
    }
  }

  return edgeCount === n - 1 ? totalWeight : -1;
}

function prim(n: number, edges: [number, number, number][]): number {
  const graph: number[][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    graph[u].push([v, w]);
    graph[v].push([u, w]);
  }

  const visited = new Set<number>();
  const minHeap: [number, number][] = [[0, 0]]; // [weight, node]
  let totalWeight = 0;

  while (visited.size < n && minHeap.length) {
    const [weight, node] = minHeap.shift()!;
    if (visited.has(node)) continue;
    visited.add(node);
    totalWeight += weight;

    for (const [neighbor, edgeWeight] of graph[node]) {
      if (!visited.has(neighbor)) {
        minHeap.push([edgeWeight, neighbor]);
        minHeap.sort((a, b) => a[0] - b[0]);
      }
    }
  }

  return visited.size === n ? totalWeight : -1;
}

function topologicalSort(n: number, edges: number[][]): number[] {
  const graph: number[][] = Array.from({ length: n }, () => []);
  const indegree = Array(n).fill(0);

  for (const [u, v] of edges) {
    graph[u].push(v);
    indegree[v] += 1;
  }

  const queue: number[] = [];
  for (let i = 0; i < n; i += 1) {
    if (indegree[i] === 0) queue.push(i);
  }

  const result: number[] = [];
  while (queue.length) {
    const node = queue.shift()!;
    result.push(node);
    for (const neighbor of graph[node]) {
      indegree[neighbor] -= 1;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === n ? result : [];
}