Prim

#include <bits/stdc++.h>

#define maxN 105
#define INF 1000000007

using namespace std;

vector < pair<int, int> > ke[maxN];
int n, m, s, ans = 0, d[maxN], trace[maxN];
bool visited[maxN];

void prim() {
    set < pair<int, int> > q;
    q.insert(make_pair(0, s));
    memset(d, INF, sizeof d); d[s] = trace[s] = 0;
    visited[s] = true;

    while (!q.empty())
    {
        pair <int, int> top = *(q.begin()); q.erase(top);
        int u = top.second;
        ans += top.first;
        visited[u] = true;
        for (int i=0; i<ke[u].size(); ++i)
        {
            int v = ke[u][i].first, w = ke[u][i].second;
            if (!visited[v] && d[v] > w)
            {
                q.erase(make_pair(d[v], v));
                d[v] = w;
                q.insert(make_pair(d[v], v));
                trace[v] = u;
            }
        }
    }
}

int main() {
    freopen("Prim.inp", "r", stdin);

    scanf("%d%d%d", &n, &m, &s);
    for (int i=0; i<m; ++i)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        ke[u].push_back(make_pair(v, w));
        ke[v].push_back(make_pair(u, w));
    }

    prim();
    cout << ans;

    return 0;
}