Prim

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("date.in");
const int inf=1e9;
int n,m,A[100][100],P[100];
void citire(){
    int i,j,k,c;
    fin>>n>>m;
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
            A[i][j]=A[j][i]=inf;
    for(int k=1; k<=m; k++){
        fin>>i>>j>>c;
        A[i][j]=A[j][i]=c;
    }
}

int main(){
    int ct=0;
    int i,k,minn,x;
    citire();
    for(i=2; i<=n; i++) P[i]=1;
    for(k=1; k<n; k++){
        minn=inf;
        for(i=1; i<=n; i++)
            if(P[i] && A[P[i]][i]<minn){
                minn=A[P[i]][i];
                x=i;
            }
        ct+=A[P[x]][x];
        for(i=1; i<=n; i++)
            if(P[i] && A[P[i]][i]>A[i][x])
                P[i]=x;
        P[x]=0;
    }
    cout<<ct;
    fin.close();
    return 0;
}