Description：
Windy有一个国家，他想建立一个军队来保护他的国家。 他召集了N个女孩和M男孩，想把他们雇佣成为他的士兵。 要无偿雇佣士兵，必须支付10000元。 女孩和男孩之间有一些关系，而Windy可以利用这些关系来降低他的成本。 如果女孩x和男孩y有关系，并且其中一个已经被收集，Windy可以以10000-d的价格雇佣另一个。 现在给予女孩和男孩之间的所有关系，你的任务是找到Windy必须支付的最少的钱。 请注意，雇佣一名士兵时只能使用一种关系。
Input：
第一行输入是测试用例的数量。
每个测试用例的第一行包含三个整数N，M和R.
然后是R行，每行包含三个整数xi，yi和di。
每个测试用例前都有一个空白行。
1≤N，M≤10000
0≤R≤50000，0≤xi<N，0≤yi<M，0 <di <10000
Output：
对于每个测试用例，都会在一行中输出答案。
Sample Input：
5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781
5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133
Sample Input：
71071
54223
Analysis：
首先，我们可以发现这是一个二分图！
然后，看了很久，我们发现好像这个二分图的性质并没有什么用。
如果有一些点被一些线连在了一起（连通块），那我们发现，只要有一个点花10000块钱买了下来，剩下的点都可以得到优惠，优惠的价格便是边权。
那相当于，一条边能对连接他的两个端点产生优惠，换而言之，其中一个点的价格便变成了（10000-边权）。
于是我们发现，便是在一个连通块里求最小生成树（边权改为10000-输入值的边权），在加上连通块的个数即可。
Code：
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll long long
#define inf (1<<29)
#define maxn 10005
#define maxe 50005
using namespace std;
int T,n,m,ec,blk,ans;
int fa[maxn<<],vis[maxn<<];
struct E{
int u,v,val;
inline int operator < (const E &a)const{
return val<a.val;
}
}e[maxe];
inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
} int mst()
{
int sum=;RG fu,fv;
rep(i,,n+m) fa[i]=i;
sort(e+,e++ec);
rep(i,,ec)
{
fu=find(e[i].u),fv=find(e[i].v);
if(fu!=fv) sum+=e[i].val,fa[fu]=fv;
}
return sum;
} int main()
{
T=read();
while(T--)
{
n=read(),m=read(),ec=read();
rep(i,,ec) e[i].u=read()+,e[i].v=read()+n+,e[i].val=-read();
ans=mst();
int bl;blk=;
rep(i,,n+m)
{
bl=find(i);
if(!vis[bl]) vis[bl]=,blk++;
}
cout<<blk*+ans<<endl;
memset(vis,,sizeof(vis));
}
return ;
}