http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1212

/* Prim */
#include"iostream"
#include"algorithm"
#include"queue"
#include"cstring"
using namespace std;
const int maxn=1e3+5;
int head[maxn],tot;
int N,M;
struct Edge
{
    int to,next,v;
};
Edge E[100005];
void AddEdge(int aa,int bb,int v)
{
    E[++tot].to=bb;
    E[tot].v=v;
    E[tot].next=head[aa];
    head[aa]=tot;
}
struct AAA
{
    int id,v;
    AAA(){}
    AAA(int id,int v):id(id),v(v){}
    bool operator<(const AAA &a)const
    {
        return a.v<v;
    }
};
int Prim(int st)
{
    int res=0;
    priority_queue<AAA>que;
    bool vis[maxn];
    int dis[maxn];
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    for(int i=head[st];i!=-1;i=E[i].next)
    {
        int t=E[i].to;
        int v=E[i].v;
        dis[t]=v;
        que.push(AAA(t,v));
    }
// for(int i=1;i<=N;i++)cout<<dis[i]<<" ";
// cout<<endl;
    dis[st]=0;
    vis[st]=1;
    while(!que.empty())
    {
        AAA u=que.top();
        que.pop();
        if(vis[u.id])continue;
        vis[u.id]=1;
        res+=u.v;
// cout<<"u.id="<<u.id<<endl;
        for(int i=head[u.id];i!=-1;i=E[i].next)
        {
            int t=E[i].to;
            int v=E[i].v;
            if(vis[t]==0&&v<dis[t])
            {
                dis[t]=v;
                que.push(AAA(t,v));
            }
        }
    }
    return res;
}
int main()
{
    while(cin>>N>>M)
    {
        tot=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=M;i++)
        {
            int t1,t2,v;
            cin>>t1>>t2>>v;
            AddEdge(t1,t2,v);
            AddEdge(t2,t1,v);
        }
        int res=Prim(1);
        cout<<res<<endl;
    }
}