记录编号	572168	评测结果	AAAAAAAAAA
题目名称	醉笑圣城书	最终得分	100
用户昵称	该账号已注销	是否通过	通过
代码语言	C++	运行时间	1.400 s
提交时间	2022-06-28 16:40:54	内存使用	25.91 MiB

#include<bits/stdc++.h>
using namespace std;
struct abc{
    int x,y,z,l;
}e[2000100];
long long n,m,cnt=0,fa[100010]={0},zx=0,s,pt;
bool cmp(abc x,abc y)
{
    return x.z<y.z;
}
bool cmp2(abc x,abc y)
{
    return x.l<y.l;
}
int get(int x)
{
    if(x==fa[x])return x;
    else return fa[x]=get(fa[x]);
}
int zxs(int x)
{
    int zx=0;
    e[pt].z=x;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x=get(e[i].x);
        int y=get(e[i].y);
        if(x==y||e[i].z==-1)continue;
        fa[x]=y;
        zx+=e[i].z;
    }
    sort(e+1,e+m+1,cmp2);
    return zx;
}
int main(){
    freopen("zxscs.in","r",stdin);
    freopen("zxscs.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].x>>e[i].y>>e[i].z;
        if(e[i].z==-1)
        {
            pt=i;
        }
        e[i].l=i;
    }
    cin>>s;
    int ans=s-zxs(0);
    cout<<ans<<endl;
    return 0;
}