题目描述
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 条公路，满足上面的条件。
输入
第1行输入有3个数 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行只有一个数据，表示花费最大的公路的花费。
接下来的n−1 行，每行有两个正整数 t 和 p， 表示在输入的第 t 对（按照输入的顺序，从 1 开始标号）景点之间修建 p 级公路。n−1 条公路的输出必须按 t 的大小递增顺序进行，如果有多个方案使花费最大的公路花费最小，那么输出任意一个都可以。
4 2 5
1 2 6 5
1 3 3 1
2 3 9 4
2 4 6 1