markdown

C. Jeremy Bearimy

欢迎！一切都很好。

你已经来到了“中庸之地”，这是介于“善之地”和“恶之地”之间的地方。你被分配了一项任务，这项任务要么让人们更幸福，要么让他们永远受折磨。

你有一份名单，上面有 $k$ 对人，这些人都来到了一个新建的居住区。你需要将 $2k$ 个人分配到 $2k$ 栋房子中。每个人恰好是一栋房子的居民，每栋房子也恰好有一个居民。

当然，在这个社区里，人们可以互相拜访。这里有 $2k-1$ 条道路，每条道路连接两栋房子。通过一条道路需要花费一定的时间，具体时间会在输入中给出。社区的设计使得从任何一栋房子出发，到其他任何一栋房子，都恰好有一条由不同道路组成的路径。换句话说，以房子为顶点、道路为边的图是一棵树。

事实上，这 $k$ 对人其实是灵魂伴侣。我们将他们从 $1$ 到 $k$ 编号。我们用 $f(i)$ 表示第 $i$ 对灵魂伴侣互相到对方房子所需的时间。

如前所述，你需要将 $2k$ 个人分配到 $2k$ 栋房子中。你有两个任务，一个来自“善之地”的实体，另一个来自“恶之地”的实体。具体如下：

• 第一个任务（来自善之地）：将人们分配到房子中，使得所有 $f(i)$ 的总和最小。我们将这个最小化的总和记为 $G$。这样可以确保灵魂伴侣能够轻松高效地互相拜访；
• 第二个任务（来自恶之地）：将人们分配到房子中，使得所有 $f(i)$ 的总和最大。我们将这个最大化的总和记为 $B$。这样可以确保灵魂伴侣难以互相拜访。

请问 $G$ 和 $B$ 分别是多少？

输入

第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。接下来的若干行包含每个测试用例的描述。

每个测试用例的第一行包含一个整数 $k$（$1 \le k \le 10^5$），表示灵魂伴侣的对数。接下来的 $2k-1$ 行描述道路；其中第 $i$ 行包含三个空格分隔的整数 $a_i$、$b_i$ 和 $t_i$，表示第 $i$ 条道路连接房子 $a_i$ 和 $b_i$，通过这条道路需要花费 $t_i$ 单位时间（$1 \le a_i, b_i \le 2k$，$a_i \neq b_i$，$1 \le t_i \le 10^6$）。保证给出的道路构成一棵树。

保证单个文件中所有 $k$ 的总和不超过 $10^5$。

输出

对于每个测试用例，输出一行，包含两个空格分隔的整数 $G$ 和 $B$。

样例

输入

2
3
1 2 3
3 2 4
2 4 3
4 5 6
5 6 5
2
1 2 1
1 3 2
1 4 3

输出

15 33
6 6

注释

对于样例中的第一个测试用例，最小总和 $G = 15$。一种可行的分配方式如下：

• 第一对灵魂伴侣被分配到房子 $1$ 和 $6$，得到 $f(1) = 5$；
• 第二对灵魂伴侣被分配到房子 $3$ 和 $4$，得到 $f(2) = 6$；
• 第三对灵魂伴侣被分配到房子 $2$ 和 $5$，得到 $f(3) = 4$。

注意 $f(i)$ 的总和为 $5 + 6 + 4 = 15$。

最大总和 $B = 33$。一种可行的分配方式如下：

• 第一对灵魂伴侣被分配到房子 $1$ 和 $4$，得到 $f(1) = 6$；
• 第二对灵魂伴侣被分配到房子 $3$ 和 $6$，得到 $f(2) = 14$；
• 第三对灵魂伴侣被分配到房子 $2$ 和 $5$，得到 $f(3) = 13$。

注意 $f(i)$ 的总和为 $6 + 14 + 13 = 33$。