题目描述

给出一个 $n$ 个点 $m$ 条边的无向图，第 $i$ 条边有两个权值 $a_i$ 和 $b_i$ 。

求该图的一棵生成树 $T$ ，使得

$$\left(\sum_{e\in T}a_e\right)\times\left(\sum_{e\in T}b_e\right) $$

最小。

输入格式

第一行两个正整数 $n,m$ 。

下 $m$ 行，每行 $4$ 个整数 $u_i,v_i,a_i,b_i$ ，表示第 $i$ 条边连接 $u_i$ 和 $v_i$ ，权值为 $a_i$ 和 $b_i$ 。

点的编号为 $0\sim n-1$ 。

输出格式

假设你求出的生成树为 $T$ ，你需要输出一行两个整数，分别为 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 。

如果有多解，请输出 $\displaystyle\sum_{e\in T}a_e$ 最小的那个。

4 5
0 1 1 2
0 2 2 3
0 3 1 5
1 3 3 4
2 3 1 3

3 10

提示

对于 $100\%$ 的数据，$1\leq n\leq 200,1\leq m\leq 10000,0\leq a_i,b_i\leq 255$ 。