题目描述

有 $n$ 个城市（编号从 $0\dots n-1$），$m$ 条公路（双向的），从中选择 $n-1$ 条边，使得任意的两个城市能够连通，一条边需要的 $c$ 的费用和 $t$ 的时间，定义一个方案的权值 $v$ 为 $n-1$ 条边的费用和 $\times$ $n-1$条边的时间和，你的任务是求一个方案使得 $v$ 最小。

输入格式

第一行两个整数 $n,m$，接下来每行四个整数 $a,b,c,t$，表示有一条公路连接城市 $a$ 与城市 $b$ 需要 $t$ 时间和 $c$ 费用。

输出格式

仅一行两个整数 $sumc,sumt$,（$sumc$ 表示使得 $v$ 最小时的费用和，$sumc$表示最小的时间和） 如果存在多个解使得 $sumc\times sumt$ 相等，输出 $sumc$ 最小的。

样例输入

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

样例输出

279 501

数据规模与约定

有 $5\%$ 的数据 $m=n-1$。

有 $40\%$ 的数据有 $t=c$。

对于 $100\%$ 的数据 $1\le n\le 200$，$1\le m\le 10^4$，$0\le a,b\le n-1$，$0\le t,c\le 255$。