题目背景

这是 $CSP-J$ 模拟赛的 $T3$ 。

题目描述

给定一棵 $n$ 个节点的树,树上边权均为正整数。

定义这棵树的生成完全图为一个 $n$ 个节点的完全图，图中两点 $u,v$ 的边权为这两点在树上简单路径上的边权和。

请你求出这张完全图的最小生成树和最大生成树，分别输出两种生成树的边权之和。

输入格式

输入多行。

第一行输入一个正整数 $n$.

接下来 $n-1$ 行，每行 $3$ 个整数 $u,v,w$ ， 表示 $u,v$ 之间有一条边权为 $w$ 的边。

输出格式

输出一行。

一行输出两个整数，分别表示最小生成树和最大生成树的边权和。

样例 #1

样例输入 #1

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

样例输出 #1

5 13

样例 #2

样例输入 #2

8
1 2 716487
2 3 804152
1 4 592006
3 5 613755
1 6 613771
5 7 903188
6 8 122044

样例输出 #2

4365403 21539678

提示

【样例解释】：

对于第一组样例的最大生成树，一种可行的方法是：

$1 \to 5 (2),2 \to 3 (2),2 \to 5(3) , 2 \to 6(3) ,4 \to 6(3) $ , 边权和为 $13$.

【数据范围】：

$Subtask0 (25pts)$ : $n \le 2000$.

$Subtask1 (20pts)$ : 保证第 $i$ 条边连接节点 $i$ 和 $i+1$.

$Subtask2 (20pts)$ : 保证第 $i$ 条边连接节点 $1$ 和 $i+1$.

$Subtask3 (20pts)$ : $n \le 2 \times10^5$.

$Subtask4 (15pts)$ : 无特殊限制.

对于 $100\%$ 的数据，保证 $1 \le n \le 10^6,0 \le w \le 10^6$，保证输入给定的是一棵树。