```cpp
#include<bits/stdc++.h>
using namespace std;
struct edge {
int u;
int v;
int w;
};
struct edge e[10000000];
int n,m;
int f[10000010]={0},count1=0;
long long sum=0;
int getf(int v)
{
if(f[v]==v)
return v;
else
{
f[v]=getf(f[v]);
return f[v];
}
}
int merge(int v,int u)
{
int t1,t2;
t1=getf(v);
t2=getf(u);
if(t1!=t2)
{
f[t2]=t1;
return 1;
}
return 0;
}
void quicksort(int left,int right)
{
int i,j;
struct edge t;
if(left>right)
return;
i=left;
j=right;
while(i!=j) {
while(e[j].w>=e[left].w && i<j)
j--;
while(e[i].w<=e[left].w && i<j)
i++;
if(i<j) {
t=e[i];
e[i]=e[j];
e[j]=t;
}
}
t=e[left];
e[left]=e[i];
e[i]=t;
quicksort(left,i-1);
quicksort(i+1,right);
return;
}
int main()
{
int n,m,s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
quicksort(1,m);
int left=1,right=10000,mid;
while(left<right)
{
mid=(left+right)/2;
int left1=1,right1=m,mid1;
while(left1<right1)
{
mid1=(left+right)/2;
if(e[mid1].w>mid)
right1=mid1-1;
else
left1=mid1+1;
}
for(int i=1;i<=mid1;i++)
{
if(merge(e[i].u,e[i].v))
{
count1++;
sum+=e[i].w;
}
if(count1==n-1)
break;
}
if(count1!=n-1)
left=mid+1;
else
right=mid-1;
}
return 0;
}
```
by hayoon @ 2023-12-02 09:59:25
https://www.luogu.com.cn/record/131818791
https://www.luogu.com.cn/record/131819117
by __My0217__ @ 2023-12-02 10:02:25