题目描述

OI 岛上有 $n$ 个景点，编号为 $1$ 到 $n$。现在需要修建公路系统连接所有景点。

每条公路可以连接两个景点，且有两种类型：

• 一级公路：车速快，但修建费用较高。
• 二级公路：车速慢，但修建费用较低。

目标是选择恰好 $n-1$ 条不同的公路，使得所有景点连通，并且其中至少包含 $k$ 条一级公路。在满足条件的前提下，要求使得所选公路中花费最大的那条公路的花费尽可能小（即最小化最大边权）。

你的任务是：在给定的可修建公路列表中，选择满足条件的 $n-1$ 条公路，并输出方案。

输入格式

第一行包含三个整数 $n, k, m$，分别表示景点数、所需一级公路的最少条数、以及可修建的公路条数。

接下来 $m$ 行，每行包含四个正整数 $a, b, c_1, c_2$，表示可以在景点 $a$ 和 $b$ 之间修建公路。若修建一级公路，花费为 $c_1$；若修建二级公路，花费为 $c_2$。

输入保证 $a \neq b$，且 $c_1 \ge c_2$。

输出格式

第一行输出一个整数，表示所选公路中花费最大的公路的花费。

接下来 $n-1$ 行，每行输出两个整数 $t$ 和 $p$：

• $t$ 表示你选择修建输入中的第 $t$ 条公路（按照输入顺序，从 $1$ 开始编号）。
• $p$ 表示修建的公路类型（$p=1$ 为一级公路，$p=2$ 为二级公路）。

如果有多组解使得最大花费最小，输出任意一组均可。

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

6
1 1
2 1
4 1

数据规模与约定

对于全部的测试点，保证 $1 \le n \le 10 ^ 4$，$0 \le k \le n-1 \le m \le 2 \times 10 ^ 4$；$1 \le a,b \le n$，$1 \le c_1, c_2 \le 3 \times 10 ^ 4$。