树生图生树

题目描述

奶龙有一棵 $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$.

数据范围：

对于 $30\%$ 的数据 : $n \le 2000$.

对于另外 $10\%$ 的数据 : 保证第 $i$ 条边连接节点 $i$ 和 $i+1$.

对于另外 $10\%$ 的数据 : 保证第 $i$ 条边连接节点 $1$ 和 $i+1$.

对于另外 $30\%$ 的数据 : $n \le 2 \times10^5$.

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

本题输入量较大，请注意使用较快的读入方式。