A 修公路

时间限制 : - MS 空间限制 : 65536 KB

评测说明 : 时限1000ms

问题描述

某岛国有n个小岛构成(编号1到n)，该国政府想要通过n-1条双向公路将这些小岛连接起来，使得任意两个岛屿之间都能相互到达。公路有两种，一种是高速公路，车速快，建设花费大；另一种是普通公路，车速慢，建设花费少。该国政府不想在一条公路上花费过多的钱，但又要求修建的公路中至少有k条高速公路。所以政府希望，在满足上述条件的情况下，使得最贵的一条公路花费尽可能少，请你帮忙计算出其中最贵一条公路的价格。

输入格式

第一行，三空格间隔的整数n,k,m，其中m表示有m对岛屿间可以修路。
接下来以下的m行，每行四个正整数a,b,c1,c2 表示在岛屿a与b 之间修高速公路花费c1块钱,修普通公路,花费c2块钱。

输出格式

一个整数表示最贵那条公路的费用。

样例输入 1

4 2 4
1 2 6 5
1 3 3 1
2 4 6 1
3 4 4 2

样例输出 1

样例输入 2

4 1 5
1 2 6 5
1 3 3 1
2 3 9 4
2 4 6 1
3 4 4 3

样例输出 2

样例输入 3

10 4 19
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

样例输出 3

提示

对于30%的数据， 1<=n<=1000 0<=k<=10 n-1<=m<=3000

对于100%的数据，1<=n<=10000 0<=k<=n-1 n-1<=m<=20000

巴特西