文件详细信息

下载本文件

本文件的大小为 1453 字节。

#include<algorithm>
#include<cstdio>
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
const int maxn=100005,maxm=100005;
bool chosen[maxn];
int special[maxn];
int t,n,m,k,u,v,w,a;
struct Edge{
	int u,v,w;
}edge[maxm];
bool operator<(Edge a,Edge b){
	if(special[a.u]+special[a.v]!=special[b.u]+special[b.v])return special[a.u]+special[a.v]<special[b.u]+special[b.v];
	return a.w<b.w;
}
int ecnt;
int fa[maxn];
int find(int a){
	return a==fa[a]?a:fa[a]=find(fa[a]);
}
long long answer;
int main(){
	t=read();
	register int i;
	while(t--){
		n=read(),m=read();
		ecnt=0,answer=0ll;
		special[0]=1;
		for(i=1;i<=n;i++)special[i]=0;
		for(i=1;i<=n;i++)chosen[i]=false;
		for(i=1;i<=n;i++)fa[i]=i;
		for(i=1;i<=m;i++){
			u=read(),v=read(),w=read();
			edge[++ecnt]=Edge{u,v,w};
		}
		k=read();
		for(i=1;i<=k;i++)special[read()]=1;
		if(n==2)goto skip;
		for(i=1;i<=m;i++)
			if(special[edge[i].u]&&special[edge[i].v])
				edge[i]={0,0,0x3f3f3f3f};
		skip:;
		std::sort(edge+1,edge+m+1);
		ecnt=0;
		for(i=1;i<=m;i++){
			u=edge[i].u,v=edge[i].v,w=edge[i].w;
			if(special[u]&&chosen[u])continue;
			if(special[v]&&chosen[v])continue;
			if(find(u)==find(v))continue;
			chosen[u]=chosen[v]=true;
			fa[find(u)]=find(v);
			answer+=w;
			ecnt++;
			if(ecnt==n-1)break;
		}
		if(ecnt==n-1)printf("%lld\n",answer);
		else puts("Impossible");
	}
	return 0;
}