問題文

1 から N までの番号がついた、頂点 1 を根とする N 頂点の根付き木があります。i 番目の辺は頂点 A_i と頂点 B_i を結ぶ辺です。

各頂点には重みが付いており、頂点 v の重みは W_v です。

あなたの目標は次の操作を任意の回数行い、最終的に 1 頂点からなる木にすることです。

• 根から伸びるパスを 1 つ選び、含まれる辺を全て縮約して新しい根とする。そして、新しい根の重みをパスに含まれていた頂点の重みの総和 S に設定し、コストに S を加算する。

目標を達成する操作列で操作回数が最小となるもののうち、かかるコストの最小値と最大値を求めてください。

制約

• 入力は全て整数
• 2 \le N \le 2 \times 10^5
• 1 \le A_i,B_i \le N
• 1 \le W_v \le 10^8
• 入力で与えられるグラフは木

入力例 1

4
1 2
1 3
2 4
20 25 1 5

出力例 1

72 101

1 頂点の木にするための最小の操作回数は 2 回です。

最初にパス 1-2-4 を選ぶと、新しい根（頂点 5 とする）と頂点 3 がつながった状態になり、S=50 が根の重みになります。次に、パス 5-3 を選ぶと木が重み S=51 の 1 頂点となり操作が終了します。このときのコストは 50+51=101 となり、 2 回で目標を達成するときのコストの最大値をとります。

また、パス 1-3 （新しい根を頂点 5 とする）、パス 5-2-4 の順に操作するとコストは 21+51=72 となり、2 回で目標を達成するときのコストの最小値をとります。

入力例 2

10
2 4
3 8
7 9
6 3
2 1
9 5
9 6
3 10
9 2
19359725 62617217 96402215 25620070 46288197 40930485 37441368 32164537 69968419 79525817

出力例 2

1525009090 2231445426