NetLine 公司希望为 $N$ 个城镇提供宽带互联网服务。为此，只需在城镇之间构建一个包含 $N-1$ 条宽带链路的网络，使得消息可以在该网络中的任意两个城镇之间传输。NetLine 已经确定了所有可以构建直接链路的城镇对。对于每一条可能的链路，他们都知道构建该链路所需的成本和时间。

公司希望同时最小化构建整个网络所需的总时间（链路逐条构建）和总金钱。由于他们无法在两个标准之间做出选择，他们决定使用以下公式来评估一个网络的价值：

$\text{SumTime} = \text{构建所选链路所花费的时间之和}$ $\text{SumMoney} = \text{构建所选链路所花费的金钱之和}$ $V = \text{SumTime} \times \text{SumMoney}$

任务

找到一组包含 $N-1$ 条链路的构建方案，使得价值 $V$ 最小。

输入格式

输入的第一行包含整数 $N$（城镇数量）和 $M$（可以连接的城镇对数量）。城镇编号从 $0$ 到 $N-1$。接下来的 $M$ 行，每行包含四个整数 $x, y, t$ 和 $c$，表示城镇 $x$ 和城镇 $y$ 之间可以建立一条耗时为 $t$、成本为 $c$ 的链路。

输出格式

输出的第一行打印两个数字：最优解（即价值 $V$ 最小的解）中的总时间 ($\text{SumTime}$) 和总金钱 ($\text{SumMoney}$)，中间用一个空格隔开。接下来的 $N-1$ 行描述要构建的链路。每行包含一对数字 $(x, y)$，描述一条要构建的链路（该链路必须是输入文件中描述的可能链路之一）。这些链路对可以以任意顺序打印。当存在多个解时，你可以打印其中任意一个。

数据范围

• $1 \le N \le 200$
• $1 \le M \le 10\,000$
• $0 \le x, y \le N-1$
• $1 \le t, c \le 255$
• 有一个测试用例满足 $M = N - 1$
• $40\%$ 的测试用例满足对于每条可能的链路都有 $t = c$

样例

输入 1

5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92

输出 1

279 501
2 1
0 3
0 2
3 4