rt。

#include<bits/stdc++.h>
using namespace std;
int f[500005];
int zx(int x){return x==f[x]?x:f[x]=zx(f[x]);}
struct edge{int x,y,t;long long v;}e[500005],t[500005];
edge a0[500005],a1[500005],a2[500005];
int cnt1=0,cnt2=0;
int n,m,k,s;
bool c1(edge x,edge y){return x.v==y.v?x.x<y.x:x.v<y.v;}
bool chs[500005];
int solve(int mid){
	memset(chs,0,sizeof(chs));
	for(int i=1;i<=cnt1;i++)a2[i]=a0[i],a2[i].v+=mid;
	merge(a1+1,a1+1+cnt2,a2+1,a2+1+cnt1,t+1,c1);
	for(int i=1;i<=n;i++)f[i]=i;
	int num=0;
	for(int i=1;i<=m;i++){
		int xx=zx(t[i].x),yy=zx(t[i].y);
		if(xx==yy)continue;
		chs[t[i].t]=1,num+=(t[i].x==1),f[xx]=yy;
	}
	return num;
}
int calc(int mid){
	for(int i=1;i<=m;i++){
		t[i]=e[i],chs[i]=0;
		if(e[i].x==1)t[i].v+=mid;
	}
	for(int i=1;i<=n;i++)f[i]=i;
	sort(t+1,t+1+m,[&](edge x,edge y){return x.v==y.v?x.x>y.x:x.v<y.v;});
	int num=0;
	for(int i=1;i<=m;i++){
		int xx=zx(t[i].x),yy=zx(t[i].y);
		if(xx==yy)continue;
		chs[t[i].t]=1,num+=(t[i].x==1),f[xx]=yy;
	}
	return num;
}
void ans(int mid,int k){
	memset(chs,0,sizeof(chs));
	for(int i=1;i<=cnt1;i++){a2[i]=a0[i];a2[i].v+=mid;} 
	merge(a1+1,a1+1+cnt2,a2+1,a2+1+cnt1,t+1,c1);
	for(int i=1;i<=n;i++)f[i]=i;
	int num=0;
	long long tmp=0;
	for(int i=1;i<=m;i++){
		int xx=zx(t[i].x),yy=zx(t[i].y);
		if(xx==yy)continue;
		if(t[i].x==1&&k==num)continue;
		chs[t[i].t]=1,num+=(t[i].x==1),f[xx]=yy;
		tmp+=t[i].v-(t[i].x==1)*mid;
	}
	cout<<tmp<<"\n";
}
bool conn(){
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int xx=zx(e[i].x),yy=zx(e[i].y);
		f[xx]=yy;
	}
	for(int i=1;i<=n;i++)if(zx(i)^zx(1))return 0;
	return 1;
}
void dswap(int &x,int t){x==1?x=t:x==t?x=1:0;}
int main(){ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
	cin>>n>>m>>s>>k;
	for(int i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y>>e[i].v,dswap(e[i].x,s),dswap(e[i].y,s);
		if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
		e[i].t=i;
	}
	for(int i=1;i<=m;i++)e[i].x==1?a0[++cnt1]=e[i]:a1[++cnt2]=e[i];
	sort(a0+1,a0+1+cnt1,c1),sort(a1+1,a1+1+cnt2,c1);
	int l=-1e9,r=1e9,las=0,mid;
	bool flg=0;
	while(l<=r){
		mid=l+r>>1;
		if(solve(mid)>=k)flg=1,las=mid,l=mid+1;
		else r=mid-1;
	}
	int v=calc(las);
	if(v>k||!flg||!conn())cout<<"Impossible\n";
	else ans(las,k);
	return 0;
}

给出 hack 数据也可以，谢谢