rt，悬赏1关注。

并非使用二分，使用Prim.

正如代码里，将与 S 有关的边单独储存并进行Prim，其余边二次 Prim，时间复杂度 $\Theta(m)$。70分，记录

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;

struct Edge
{
	int L1,L2;
	long long Len;
	Edge(){L1 = L2 = Len = 0;}
};
bool cmp(Edge a,Edge b){return a.Len < b.Len;}

bitset<500005> Vist;
Edge E[500005],R[500005];
int tot;

int Fa[50004];
int Find(int x)
{
	if(x == Fa[x])
		return x;
	return Fa[x] = Find(Fa[x]);
}

int N,M,S,K;
long long Cost;

int main()
{
	scanf("%d%d%d%d",&N,&M,&S,&K);
	for(int i = 1 ; i<= N ; i++)
		Fa[i] = i;
	for(int i = 1 ; i<= M ; i++)
	{
		scanf("%d%d%lld",&E[i].L1,&E[i].L2,&E[i].Len);
		if(E[i].L1 == S or E[i].L2 == S)
			R[++tot] = E[i], i--, M--;
	}
	if(tot < K)
	{
		puts("Impossible");
		return 0;
	}
	sort(R+1,R+tot+1,cmp);
	int Num = 0;
	int i;
	for(i = 1 ; i<= tot && Num < K ; i++)
	{
		if(Find(R[i].L1) == Find(R[i].L2))
			continue;
		if(R[i].L1 > R[i].L2)
			swap(R[i].L1,R[i].L2);
		Fa[Find(R[i].L1)] = Find(R[i].L2);
		Cost += R[i].Len;
		Vist[i] = true;
		Num++;
	}
	i = 1;
	while(i <= tot && Num < K)
	{
		if(!Vist[i])
		{
			if(R[i].L1 > R[i].L2)
				swap(R[i].L1,R[i].L2);
			Fa[Find(R[i].L1)] = Find(R[i].L2);
			Cost += R[i].Len;
			Vist[i] = true;
			Num++;
		}
		i++;
	}
	sort(E+1,E+M+1,cmp);
	for(i = 1 ; i<= M ; i++)
	{
		if(Find(E[i].L1) == Find(E[i].L2))
			continue;
		if(E[i].L1 > E[i].L2)
			swap(E[i].L1,E[i].L2);
		Fa[Find(E[i].L1)] = Find(E[i].L2);
		Cost += E[i].Len;
	}
	for(i = 1 ; i< N ; i++)
	{
		if(Find(i) != Find(i+1))
		{
			puts("Impossible");
			return 0;
		}
	}
	printf("%lld\n",Cost);
	return 0;
}