1361: 真是k对苦命鸳鸯

ajj 和 xjj 真是一对苦命鸳鸯（流泪）

你已抵达「中立之境」——介于「喜糖」与「大份」之间的地带。你被赋予一项任务：或让世人更幸福，或令其承受永恒煎熬。

现在你有一份包含 $k$ 对居民的名单，他们刚迁入一片新社区。你需要将这 $2k$ 位居民分配至 $2k$ 栋房屋中。每人恰好入住一栋房屋，每栋房屋也恰好入住一人。

在这片社区中，居民可以拜访友人。这里共有 $2k−1$ 条道路，每条道路连接两栋房屋，且通行需耗费特定时间（具体时长将在输入中给出）。社区经过精心规划，从任意一栋房屋出发，到其他任何房屋都存在唯一一条不重复的道路序列。换言之，以房屋为顶点、道路为边构成的图是一棵树。

实际上，这 $k$ 对人正是 $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$ 的总和不超过 $3 \times 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