Bytetown 有 $n$ 座房子，编号为 $1, 2, \dots, n$。每座房子里住着一个人。小 Q 住在 1 号房子。这 $n$ 座房子之间有 $n-1$ 条双向街道相连，构成一棵树。在本题中，$S(u, v)$ 表示从房子 $u$ 到房子 $v$ 的最短路径上所有房子组成的集合。

Bytetown 的电话线路网络包含 $m$ 条不同的线路。第 $i$ 条线路可以用五个整数 $a_i, b_i, c_i, d_i$ 和 $w_i$ 来描述，这意味着对于集合 $S(a_i, b_i) \cup S(c_i, d_i)$ 中的任意两座不同的房子 $u$ 和 $v$，它们之间可以进行一次通话，费用为 $w_i$ 美元。

小 Q 现在计划在他的房子里举办一场大型派对，他想邀请尽可能多的人。每个知道邀请信息的人都可以向其他人拨打任意数量的电话来传播邀请，但没有人可以离开他们的房子。

编写一个程序，求出能够参加派对的人数的最大值，以及达到该最大人数所需的最小总费用。小 Q 本人也应计入总人数中。

输入格式

第一行包含两个整数 $n$ 和 $m$：房子数量和电话线路数量 ($1 \le n, m \le 10^5$)。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示房子 $u$ 和 $v$ 之间的一条双向街道。保证这些房子和街道构成一棵树。

接下来的 $m$ 行，第 $i$ 行包含五个整数 $a_i, b_i, c_i, d_i$ 和 $w_i$，描述一条电话线路 ($1 \le a_i, b_i, c_i, d_i \le n, 1 \le w_i \le 10^9$)。

输出格式

输出一行，包含两个整数：能够参加派对的人数的最大值，以及达到该最大人数所需的最小总费用。

样例

样例输入 1

5 2
1 2
1 3
2 4
2 5
1 3 2 4 100
2 2 4 2 10

样例输出 1

4 210

说明

一种可能的方案如下：

第一步：1 号房子使用线路 1 给 2 号房子打电话，费用为 100。 第二步：1 号房子使用线路 1 给 3 号房子打电话，费用为 100。 第三步：2 号房子使用线路 2 给 4 号房子打电话，费用为 10。