蒟蒻又发现自己还没写过LCT……
首先显然按照权值a从小到大排序，维护b的最小生成树。然后直接扫，代价是加入b的最大值，然后动态加边，因为有边权，所以在lct中边应该理解为点。每次连接(u,v)时，若不连通则直接连起来，反之则需选择b最大的边断开。
#include<bits/stdc++.h> using namespace std; const int N=2e5+7; struct node{int a,b,x,y;}q[N]; int n,m,len,fa[N],lc[N],rc[N],rev[N],b[N],val[N],s[N],f[N]; bool cmp(node a,node b){return a.y<b.y;} int dir(int x){return x==rc[fa[x]];} int find(int x){return x==f[x]?x:f[x]=find(f[x]);} void union1(int x,int y){x=find(x),y=find(y);if(x!=y)f[x]=y;} bool isroot(int x){return!fa[x]||lc[fa[x]]!=x&&rc[fa[x]]!=x;} void pushup(int x) { s[x]=x; if(lc[x]&&val[s[lc[x]]]>val[s[x]])s[x]=s[lc[x]]; if(rc[x]&&val[s[rc[x]]]>val[s[x]])s[x]=s[rc[x]]; } void pushdown(int x) { if(rev[x]) { swap(lc[x],rc[x]); if(lc[x])rev[lc[x]]^=1; if(rc[x])rev[rc[x]]^=1; rev[x]=0; } } void rotate(int x) { int y=fa[x],z=fa[y],w=x==lc[y]?rc[x]:lc[x]; if(z&&!isroot(y))(y==lc[z]?lc[z]:rc[z])=x; fa[x]=z,fa[y]=x; if(w)fa[w]=y; if(x==lc[y])rc[x]=y,lc[y]=w;else lc[x]=y,rc[y]=w; pushup(y),pushup(x); } void splay(int x) { int len=1,y=x;b[1]=x; while(!isroot(y))b[++len]=fa[y],y=fa[y]; for(int i=len;i;i--)pushdown(b[i]); while(!isroot(x)) { if(!isroot(fa[x])) { if(dir(x)==dir(fa[x]))rotate(fa[x]); else rotate(x); } rotate(x); } pushup(x); } void access(int x) { int y=0; while(x) { splay(x),rc[x]=y; if(y)fa[y]=x; pushup(x),y=x,x=fa[x]; } } int findrt(int x) { access(x),splay(x),pushdown(x); while(lc[x])x=lc[x]; splay(x); return x; } void reverse(int x){access(x),splay(x),rev[x]^=1;} void link(int x,int y){reverse(x),fa[x]=y;} void cut(int x,int y){reverse(x),access(y),splay(y),lc[y]=fa[x]=0,pushup(y);} int query(int x,int y){reverse(x),access(y),splay(y);return s[y];} int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d%d%d%d",&q[i].a,&q[i].b,&q[i].x,&q[i].y); sort(q+1,q+m+1,cmp); for(int i=1;i<=n+m;i++)f[i]=s[i]=i; for(int i=n+1;i<=n+m;i++)val[i]=q[i-n].x; int ans=2e9; for(int i=1;i<=m;i++) { int u=q[i].a,v=q[i].b; bool flag=1; if(find(u)==find(v)) { int w=query(u,v); if(val[w]>q[i].x)cut(q[w-n].a,w),cut(w,q[w-n].b);else flag=0; } else union1(u,v); if(flag)link(u,i+n),link(i+n,v); if(find(1)==find(n))ans=min(ans,q[i].y+val[query(1,n)]); } if(ans<2e9)printf("%d",ans);else puts("-1"); }