#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
#define max 20000
using namespace std;
struct pq
{
int node,cost;
bool operator<(const pq &b)const
{
return cost>b.cost;
}
};
int prims(vector<pq>mst[],int source,int node)
{
priority_queue<pq>p;
long taken[max]={0},sum,i,j,s;
pq u,v;
v.node=source;
s=v.cost=0;
p.push(v);
while(!p.empty())
{
u=p.top();
if(taken[u.node]==0)
s+=u.cost;
taken[u.node]=1;
p.pop();
for(i=0;i<mst[u.node].size();i++)
{
if(taken[mst[u.node][i].node]==0)
{
v.node=mst[u.node][i].node;
v.cost=mst[u.node][i].cost;
p.push(v);
}
}
}
return s;
}
int main()
{
int nodes,edge,i,j,x,y,z,val;
vector<pq>mst[max];
pq v;
while(scanf("%d%d",&nodes,&edge)==2)
{
if(nodes==0&&edge==0)break;
long t=0;
for(i=0;i<max;i++)
mst[i].clear();
for(i=0;i<edge;i++)
{
cin>>x>>y>>z;
v.cost=z;
v.node=y;
mst[x].push_back(v);
v.node=x;
mst[y].push_back(v);
t=t+z;
}
val=prims(mst,0,nodes);
cout<<t-val<<endl;
}
}
#define fr(i1,m) for(int i1=0;i1<m;i1++)
#define max 20000
using namespace std;
struct pq
{
int node,cost;
bool operator<(const pq &b)const
{
return cost>b.cost;
}
};
int prims(vector<pq>mst[],int source,int node)
{
priority_queue<pq>p;
long taken[max]={0},sum,i,j,s;
pq u,v;
v.node=source;
s=v.cost=0;
p.push(v);
while(!p.empty())
{
u=p.top();
if(taken[u.node]==0)
s+=u.cost;
taken[u.node]=1;
p.pop();
for(i=0;i<mst[u.node].size();i++)
{
if(taken[mst[u.node][i].node]==0)
{
v.node=mst[u.node][i].node;
v.cost=mst[u.node][i].cost;
p.push(v);
}
}
}
return s;
}
int main()
{
int nodes,edge,i,j,x,y,z,val;
vector<pq>mst[max];
pq v;
while(scanf("%d%d",&nodes,&edge)==2)
{
if(nodes==0&&edge==0)break;
long t=0;
for(i=0;i<max;i++)
mst[i].clear();
for(i=0;i<edge;i++)
{
cin>>x>>y>>z;
v.cost=z;
v.node=y;
mst[x].push_back(v);
v.node=x;
mst[y].push_back(v);
t=t+z;
}
val=prims(mst,0,nodes);
cout<<t-val<<endl;
}
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন