#1102. Phone Call

比特镇（Bytetown）有 个房子，分别标记为 。每个房子中住着一个人。小 Q 住在房子 里。比特镇中有 条双向街道连接这些房子，形成树的结构。在这个问题中， 表示从房子 到房子 的最短路径上所有房子的集合。

比特镇的电话线路网络由 条不同的线路组成。第 条线路可以用 5 个整数 表示，这意味着，对于集合 中的任意两个不同的房子 和 ， 可以以 的费用向 打电话。

小 Q 现在计划在他家举办一个大派对，因此他希望让尽可能多的人知道这个消息。只要一个人得到了消息，就可以通过电话传递给其他人，但人不能离开自己的房子。

请你编写一个程序，计算出最多能有多少人参加这个派对，以及达到这个人数所需的最低总成本。小 Q 自己应该被包括在答案中。

第一行包含一个整数 ，表示测试用例的数量。

对于每个测试用例，输入格式如下：

1. 第一行包含两个整数 ，分别表示房子的数量和电话线路的数量。
2. 接下来的 行，每行包含两个整数 和 ，表示房子 和 之间的双向连接（即一条树的边）。
3. 接下来的 行，每行包含 5 个整数 ，表示一条电话线路。

对于每个测试用例，输出一行包含两个整数，分别表示：

1. 能参加派对的最多人数。
2. 达到该人数的最低花费。

输入样例1

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 步：小 Q（房子 1）通过线路 1 向房子 2 打电话，费用为 100。
• 第 2 步：小 Q（房子 1）通过线路 1 向房子 3 打电话，费用为 100。
• 第 3 步：房子 2 通过线路 2 向房子 4 打电话，费用为 10。

最终有 4 个人参加派对，总花费为 。