[BalkanOI2011] timeismoney | 最小乘积生成树

题目描述

给出一个 $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$ 最小的那个。

输入输出样例

输入样例 #1

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

输出样例 #1

3 10

说明

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