/* * 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);

include

using namespace std;

string ltrim(const string &); string rtrim(const string &); vector split(const string &);

int prims(int n, vector> edges, int start) { vector>> graph(n + 1);

// Constructing the graph from the given edges
for (auto& edge : edges) {
    int u = edge[0];
    int v = edge[1];
    int w = edge[2];
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

// Priority queue to store the edges based on weights
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

vector<bool> visited(n + 1, false);
visited[start] = true;

// Adding edges connected to the starting node to the priority queue
for (auto& edge : graph[start]) {
    pq.push({edge.second, edge.first});
}

int minWeight = 0;

// Applying Prim's algorithm
while (!pq.empty()) {
    pair<int, int> p = pq.top();
    pq.pop();
    int u = p.second;
    int weight = p.first;

    // If the node is already visited, continue to the next iteration
    if (visited[u]) {
        continue;
    }

    // Mark the node as visited and add its weight to the minimum weight
    visited[u] = true;
    minWeight += weight;

    // Add all the edges connected to the current node to the priority queue
    for (auto& edge : graph[u]) {
        if (!visited[edge.first]) {
            pq.push({edge.second, edge.first});
        }
    }
}

return minWeight;

}

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string first_multiple_input_temp;
getline(cin, first_multiple_input_temp);

vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

int n = stoi(first_multiple_input[0]);
int m = stoi(first_multiple_input[1]);

vector<vector<int>> edges(m);

for (int i = 0; i < m; i++) {
    edges[i].resize(3);

    string edges_row_temp_temp;
    getline(cin, edges_row_temp_temp);

    vector<string> edges_row_temp = split(rtrim(edges_row_temp_temp));

    for (int j = 0; j < 3; j++) {
        int edges_row_item = stoi(edges_row_temp[j]);

        edges[i][j] = edges_row_item;
    }
}

string start_temp;
getline(cin, start_temp);

int start = stoi(ltrim(rtrim(start_temp)));

int result = prims(n, edges, start);

fout << result << "\n";

fout.close();

return 0;

}

string ltrim(const string &str) { string s(str);

s.erase(
    s.begin(),
    find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);

return s;

}

string rtrim(const string &str) { string s(str);

s.erase(
    find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
    s.end()
);

return s;

}

vector split(const string &str) { vector tokens;

string::size_type start = 0;
string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {
    tokens.push_back(str.substr(start, end - start));

    start = end + 1;
}

tokens.push_back(str.substr(start));

return tokens;

}

python3

def prims(n, edges, start):
    
    mst = {start}
    total = 0
    edges.sort(key=lambda x: x[2])

    # Prim: Add lowest weight edge that starts anywhere in the mst and ends on any of the remaining vertices (guarantees no cycles), until no vertices remain.
    while len(mst) < n:
        for u, v, w in edges:
            if (u in mst) ^ (v in mst):
                mst = mst.union({u, v})
                total += w
                break
    return total