CF的双倍经验过了，比正确答案大

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,cnt,t,now,ans=2000000000000000000,edgesum,vis[200005],num[200005],g,s;
struct node{int fa,ls,rs,val,id,maxi,tag;}tree[200005];
struct Edge{int id,u,v,a,w;}edge[200005],edge2[200005];
map<pair<int,int>,int> mp;
bool cmp(Edge x,Edge y){return x.a<y.a;}
bool cmp2(Edge x,Edge y){return x.w>y.w;}
void pushup(int cur)
{
	if(tree[cur].val>tree[tree[cur].ls].maxi&&tree[cur].val>tree[tree[cur].rs].maxi) tree[cur].maxi=tree[cur].val,tree[cur].id=cur;
	else if(tree[tree[cur].ls].maxi>tree[tree[cur].rs].maxi) tree[cur].maxi=tree[tree[cur].ls].maxi,tree[cur].id=tree[tree[cur].ls].id;
	else tree[cur].maxi=tree[tree[cur].rs].maxi,tree[cur].id=tree[tree[cur].rs].id;
}
int get(int cur)
{
	if(tree[tree[cur].fa].ls==cur) return 0;
	if(tree[tree[cur].fa].rs==cur) return 1;
	return -1;
}
void connect(int cur,int fa,int opt)
{
	tree[cur].fa=fa;
	if(opt==0) tree[fa].ls=cur;
	if(opt==1) tree[fa].rs=cur;
}
void rotate(int x)
{
	int y=tree[x].fa;
	int z=tree[y].fa;
	int opx=get(x),opy=get(y);
	int u=0;
	if(opx==0) u=tree[x].rs;
	if(opx==1) u=tree[x].ls;
	connect(u,y,opx);
	connect(y,x,opx^1);
	connect(x,z,opy);
	pushup(x),pushup(y);
}
void pushdown(int cur)
{
	if(tree[cur].tag==0) return ;
	swap(tree[cur].ls,tree[cur].rs);
	if(tree[cur].ls!=0) tree[tree[cur].ls].tag^=1;
	if(tree[cur].rs!=0) tree[tree[cur].rs].tag^=1;
	tree[cur].tag=0;
}
void pushfa(int cur)
{
//	cout<<cur<<" "<<tree[cur].ls<<" "<<tree[cur].rs<<"\n";
	if(get(cur)!=-1) pushfa(tree[cur].fa);
	pushdown(cur);
}
void splay(int cur)
{
	if(cur==0) return ;
	pushfa(cur);
	while(get(cur)!=-1)
	{
//		cout<<"*";
		int fa=tree[cur].fa;
		if(get(fa)==-1) rotate(cur);
		else if(get(cur)==get(fa)) rotate(fa),rotate(cur);
		else rotate(cur),rotate(cur);
	}
}
void access(int cur)
{
	int son=0;
	while(cur!=0)
	{
//		cout<<"*";
		splay(cur);
		tree[cur].rs=son;
		pushup(cur);
		son=cur;
		cur=tree[cur].fa;
	}
}
void makeroot(int cur)
{
	access(cur);
	splay(cur);
	swap(tree[cur].ls,tree[cur].rs);
	if(tree[cur].ls!=0) tree[tree[cur].ls].tag^=1;
	if(tree[cur].rs!=0) tree[tree[cur].rs].tag^=1;
} 
void split(int x,int y)
{
	makeroot(x);
	access(y);
	splay(y);
}
int findroot(int cur)
{
	access(cur);
	splay(cur);
	while(tree[cur].ls!=0) pushdown(cur),cur=tree[cur].ls;
	splay(cur);
	return cur;
}
void link(int x,int y)
{
	makeroot(x);
	if(findroot(y)==x) return ;
	tree[x].fa=y;
}
void cut(int x,int y)
{
	if(findroot(x)!=findroot(y)) return ;
	split(x,y);
	if(tree[x].fa!=y||tree[x].rs!=0) return ;
	tree[x].fa=tree[y].ls=0;
	pushup(x);
}
void insert(int kth,int id,int x,int y,int w)
{
	if(x==y) return ;
	if(findroot(x)!=findroot(y))
	{
		link(x,id);link(y,id);
		vis[kth]=1;
		edgesum++;
	}
	else
	{
		split(x,y);
		if(tree[y].maxi>w)
		{
			int nid=tree[y].id;
			cut(edge[nid].u,nid);cut(edge[nid].v,nid);
			vis[num[edge[nid].id]]=0;
			link(x,id);link(y,id);
			vis[kth]=1;
		}
	}
	if(edgesum==n-1)
	{
		while(vis[now]==0) now++;
//		cout<<now<<"\n";
		ans=min(ans,edge2[now].w+edge[id].a);
	}
}
signed main()
{
	cin>>n>>m;
	now=1;
	for(int i=n+1;i<=m+n;i++){edge[i].id=i;cin>>edge[i].u>>edge[i].v>>edge[i].a>>edge[i].w;edge2[i-n]=edge[i];}
	sort(edge+n+1,edge+n+m+1,cmp);
	sort(edge2+1,edge2+m+1,cmp2);
	for(int i=1;i<=m;i++) num[edge2[i].id]=i;
	for(int i=n+1;i<=n+m;i++)
	{
		tree[i].val=tree[i].maxi=edge[i].w,tree[i].id=i;
		insert(num[edge[i].id],i,edge[i].u,edge[i].v,edge[i].w);
	}
	if(ans==2000000000000000000) ans=-1;
	cout<<ans;
	return 0;
}//