题面

---

---

$ 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;

}