OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association组织成立了，旨在建立OI island的交通系统。 OI island有n个旅游景点，不妨将它们从1到n标号。现在，OIER Association需要修公路将这些景点连接起来。一条公路连接两个景点。
公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。 OIER Association打算修n-1条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。
为了保证公路系统的效率, OIER Association希望在这n-1条公路之中,至少有k条(0 ≤ k ≤ n-1)一级公路。OIER Association也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。而你的任务就是，在给定一些可能修建的公路的情况下，选择n-1条公路，满足上面的条件。

输入描述:
第一行有三个数n(1 ≤ n ≤ 10000),k(0 ≤ k ≤ n-1),m(n-1 ≤ m ≤ 20000)，这些数之间用空格分开。
N和k如前所述，m表示有m对景点之间可以修公路。
以下的m-1行，每一行有4个正整数a,b,c1,c2 （1 ≤ a,b ≤ n,a≠b,1 ≤ c2 ≤ c1 ≤ 30000）表示在景点a与b之间可以修公路,如果修一级公路,则需要c1的花费,如果修二级公路,则需要c2的花费。

输出描述:
一个数据，表示花费最大的公路的花费。
示例1
输入
10 4 20
3 9 6 3
1 3 4 1
5 3 10 2
8 9 8 7
6 8 8 3
7 1 3 2
4 9 9 5
10 8 9 1
2 6 9 1
6 7 9 8
2 6 2 1
3 8 9 5
3 2 9 6
1 6 10 3
5 6 3 1
2 7 6 1
7 8 6 2
10 9 2 1
7 1 10 2
输出
5

#include<bits/stdc++.h>
using namespace std;
inline int read()
{ 
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){ if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){ x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=10001,M=20001,K=10001;
struct edge
{ 
	int from,to,dis,nex;
}e[2*N],ee[2*N];
int head[N],cnt1,cnt2;
void add(edge *e,int u,int v,int w,int &tot)
{ 
	e[++tot].to=v;
	e[tot].from=u;
	e[tot].dis=w;
	e[tot].nex=head[u];
	head[u]=tot;
}
int f[N];
int find(int x)
{ 
	return f[x]==x ? x : f[x]=find(f[x]);
}
bool cmp(edge a,edge b)
{ 
	if(a.dis!=b.dis)return a.dis<b.dis;
	return a.from<b.from;
}
int sum,ans;
void kruskal(edge *e,int m,int k)
{ 
	sum=0;
	for(int i=1;i<=m;++i)
	{ 
		int x=e[i].from,y=e[i].to,fx=find(x),fy=find(y);
		if(fx!=fy)
		{ 
			f[fx]=fy;
			++sum;
			ans=max(ans,e[i].dis);
		}
		if(sum==k)return;
	}
}
int n ,k , m;
int main()
{ 
	n = read();k = read();m = read();
	for(int i=1;i<=n;++i)f[i]=i;
	for(int i=1;i<m;++i)
	{ 
		int a=read(),b=read(),c=read(),d=read();
		add(e,a,b,d,cnt1);add(ee,a,b,c,cnt2);
	}
	sort(ee+1,ee+1+cnt2,cmp);
	kruskal(ee,cnt2,k);
	sort(e+1,e+1+cnt1,cmp);
	kruskal(e,cnt1,n-1-k);
	cout<<ans;
	return 0;
}