该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

After winning the silver medal, the young Muxue enrolled at Peking University. While happily walking on a forest path, he recalled an unsolved problem from the competition.

Problem Description

Young Muxue has a tree with $n$ vertices and a complete graph with $n$ vertices. Both the tree and the graph have edge weights, and every natural number less than $n-1$ appears exactly once among the edge weights of the tree. The length of an edge $u \to v$ in the complete graph is defined as the $\operatorname{mex}$ of the edge weights along the unique simple path from $u$ to $v$ in the tree.
You are given the tree, and you need to tell Muxue the total weights of the minimum spanning tree and the maximum spanning tree of his complete graph.

Input Format

The first line contains an integer $n$.
The next $n-1$ lines each contain three non-negative integers $u_i, v_i, w_i$, representing an edge in the tree.

Output Format

Output one line with two integers: the total weight of the minimum spanning tree and the total weight of the maximum spanning tree.

Sample Input/Output 1

Input

5
1 2 0
1 3 1
1 4 2
1 5 3

Output

1 5

Constraints

For all test data, it is guaranteed that:$1 \le u_i, v_i \le n \le 2\times 10^6$, $0 \le w_i < n-1$, $\forall i \neq j \le n, w_i \neq w_j$.