/* * Complete the 'prims' function below. * * The function is expected to return an INTEGER. * The function accepts following parameters: * 1. INTEGER n * 2. 2D_INTEGER_ARRAY edges * 3. INTEGER start */

function prims(edges, mst = [total = 0;

// Sort edges based on weight
usort(`$edges, function($`a, $b) {
    return `$a[2] - $`b[2];
});

// Prim's algorithm: Add the lowest weight edge that connects to the MST
while (count(`$mst) < $`n) {
    foreach (`$edges as $`edge) {
        list(`$u, $`v, `$w) = $`edge;
        `$uInMST = in_array($`u, $mst);
        `$vInMST = in_array($`v, $mst);

        // Check if one vertex is in MST and the other is not (XOR logic)
        if (`$uInMST xor $`vInMST) {
            // Add vertices to MST
            if (!`$uInMST) $`mst[] = $u;
            if (!`$vInMST) $`mst[] = $v;

            // Add weight to total
            `$total += $`w;
            break;
        }
    }
}

return $total;

}

fwrite(result . "\n");

fclose($fptr);