题面
$ solution: $
这道题很奇妙，需要对kruskal重构树有足够的了解！我们先对王牌电缆实行kruskal重构树，然后我们再来枚举每一条李牌电缆，我们将某一条李牌电缆加进这棵树中必然构成一颗基环树，然后我们必须在这个环上去掉一条王牌电缆，而这我们就可以用树上倍增来完成了！（这样做是正确的，仔细想一下为什么我们kruskal重构的树一定是最优解）
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int
using namespace std;
struct su{ //王牌电线
int x,y,v,z;
inline bool operator <(su x){return v<x.v;}
}a[200005];
struct pi{ //树的边
int to,next,v,z;
}k[100005];
struct ya{ //倍增求LCA
int x,v,z;
}f[100005][17],c;
int n,w,l,top; //意义如题
int ans1,ans2,qu,li;//后两个是存的去的哪一条王牌电线以及对应加的那一条李牌电线
int s[100005]; //并查集
int q[100005]; //BFS预处理
int dp[100005]; //这个点的深度
int tou[100005]; //连接这个点的边
bool vis[100005]; //我又没有访问过
bool shu[200005]; //这条电线我会不会用
inline int qr(){ char ch; //快读
while((ch=getchar())<'0'||ch>'9');
int res=ch^48;
while((ch=getchar())>='0'&&ch<='9')
res=res*10+(ch^48);
return res;
}
inline ya max(ya x,ya y){return x.v>y.v?x:y;}
inline ya max(ya x,ya y,ya z){return x.v>y.v?(x.v>z.v?x:z):(y.v>z.v?y:z);}
inline void print(int x,int y){ //输出
printf("%d\n",x);
for(rg i=1;i<=w;++i)
if(shu[i])printf("%d\n",i);//有用这条王牌电线就输出
printf("%d\n",y);
}
inline int get(int x){ //并查集
return s[x]==x?x:(s[x]=get(s[x]));
}
inline void add(int x,int y,int v,int z){
k[++top]=pi{y,tou[x],v,z};
k[++top]=pi{x,tou[y],v,z};
tou[y]=top; tou[x]=top-1;//加双向边
}
inline void yu(){ //树上倍增的预处理
q[1]=1;dp[1]=1;vis[1]=1;
int l=0,r=1,i;
while(l<r){ i=q[++l];
for(rg j=0;j<16;++j){
if(!f[f[i][j].x][j].x)break;
f[i][j+1]=max(f[i][j],f[f[i][j].x][j]);
f[i][j+1].x=f[f[i][j].x][j].x;//注意先后顺序防覆盖
}
for(rg j=tou[i];j;j=k[j].next){
if(vis[k[j].to])continue;
int to=k[j].to;
f[to][0].z=k[j].z;
f[to][0].v=k[j].v;
f[to][0].x=i;//
dp[to]=dp[i]+1;
vis[to]=1; q[++r]=to;//
}
}
}
inline ya ask(int x,int y){ //最近公共祖先，及其路径上的最大边权
if(dp[x]<dp[y])swap(x,y);
ya res; res.v=0;
for(rg i=16;i>=0;--i)
if(dp[f[x][i].x]>=dp[y])
res=max(res,f[x][i]),x=f[x][i].x;
for(rg i=16;i>=0;--i)
if(f[x][i].x!=f[y][i].x){
res=max(res,f[x][i]);//先取值再更新x
res=max(res,f[y][i]);
x=f[x][i].x,y=f[y][i].x;//注意先后
}else if(x==y)return res;
return max(res,f[x][0],f[y][0]);
}
inline void kruskal(){ int t=0;
for(rg i=1;i<=n;++i)s[i]=i;//最小生成树
for(rg i=1;i<=w;++i)
if(get(a[i].x)!=get(a[i].y)){
s[get(a[i].x)]=get(a[i].y);
add(a[i].x,a[i].y,a[i].v,a[i].z);
shu[a[i].z]=1;ans1+=a[i].v;++t; //我们需要同时记住这条边的信息
}
if(t==n-1)return ;
rg x,y,v,j; ans2=inf;//仅靠王牌不能联通就直接枚举用那条李边划算
for(rg i=1;i<=l;++i){
x=qr(),y=qr(),v=qr();
if(get(x)!=get(y)&&ans2>v) ans2=v,j=i;//能用的权值最小的
}print(ans2+ans1,j),exit(0);
}
int main(){
freopen("telephone.in","r",stdin);
freopen("telephone.out","w",stdout);
n=qr(),w=qr(),l=qr();
for(rg i=1;i<=w;++i)
a[i]=su{qr(),qr(),qr(),i};
sort(a+1,a+w+1);kruskal();yu();//排序，最小生成树，预处理
for(rg i=1,v;i<=l;++i){ //
c=ask(qr(),qr()); v=qr();
if(!li||ans2>ans1-c.v+v){//更新最优解
ans2=ans1-c.v+v;
shu[qu]=1;shu[c.z]=0;//要把上一个去掉的加回来！
li=i; qu=c.z;//记录去掉那条边，加上那条边
}
}print(ans2,li);//输出
return 0;
}