#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
class union_find{
public:
explicit union_find(int _n):n(_n){
par.resize(static_cast<unsigned long>(_n));
rank.resize(static_cast<unsigned long>(_n));
sizes.resize(static_cast<unsigned long>(_n));
for(int i=0;i<_n;i++){
par[i]=i;
rank[i]=0;
sizes[i]=1;
}
}
int find(int a){
if(par[a]==a)return a;
return par[a]=find(par[a]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void unite(int a,int b){
link(find(a),find(b));
}
int size(int a){
return sizes[find(a)];
}
void view(){
for(int i=0;i<n;i++){
cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":",");
}
for(int i=0;i<n;i++){
cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":",");
}
cout<<endl;
}
void init(){
for(int i=0;i<n;i++){
par[i]=i;
rank[i]=0;
sizes[i]=1;
}
}
private:
void link(int a,int b){
if(same(a,b))return;
if(rank[a]>rank[b]){
par[b]=a;
sizes[a]+=sizes[b];
sizes[b]=0;
}else{
par[a]=b;
if(rank[a]==rank[b])rank[b]++;
sizes[b]+=sizes[a];
sizes[a]=0;
}
}
int n;
vector<int> par;
vector<int> rank;
vector<int> sizes;
};
int main(){
int n,m;
while(cin>>n>>m,n){
vector<pair<int,int> > h;
for(int i=0;i<n;i++){
int a;cin>>a;
h.push_back({a,i});
}
union_find tmp(n);
vector<pair<pair<int,int>,int> > v;
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
a--;b--;
tmp.unite(a,b);
v.push_back(make_pair(make_pair(c,a),b));
}
if(tmp.size(0)!=n){
cout<<0<<endl;
continue;
}
sort(h.begin(),h.end());
reverse(h.begin(),h.end());
sort(v.begin(),v.end());
union_find uf(n);
ll ans=0;
bool ok[201];
int cont=0;
for(int i=0;i<n;i++)ok[i]=0;
for(int i=0;i<n;i++){
ok[h[i].se]=1;
if(i==n-1 || h[i].fi!=h[i+1].fi){
for(int j=0;j<m;j++){
int nowa=v[j].fi.se;
int nowb=v[j].se;
if(ok[nowa] && ok[nowb] && !uf.same(nowa,nowb)){
ans+=v[j].fi.fi;
cont++;
uf.unite(nowa,nowb);
}
}
if(cont!=i){
uf.init();
cont=0;
ans=0;
}
}
}
cout<<ans<<endl;
}
return 0;
}
- 日本語が難しかった。。
- こういう問題に当たりたくないなぁ。。