問題文

パ研ランドには N 個のアトラクションがあり、1 から N までの番号がつけられています。

また、これらのアトラクションを結ぶ道が N - 1 本あり、 1 から N - 1 までの番号がつけられています。

道 i (1 \leq i \leq N - 1) はアトラクション A_i と アトラクション B_i を双方向に結んでいます。

さらに、パ研ランドのそれぞれの道には「楽しさ」という値が設定されていて、道 i (1 \leq i \leq N - 1) の楽しさは C_i です。

パ研ランドでのアトラクション間の移動も楽しみたい hiikunZ 君のために、すべてのアトラクション i (1 \leq i \leq N) について、次の問題を解いてください。

hiikunZ 君はアトラクション i から、アトラクション i とは異なるアトラクション j (i \neq j,1 \leq j \leq N) を 1 つ決め、アトラクション i から アトラクション j に道を通る回数が最小になるように移動しようと考えています。

アトラクション j を適切に選んだとき、hiikunZ 君が通る道の「楽しさ」の平均値を最大でいくつにできるかを求めてください。

ただし、答えは整数では表せない場合があるので、答えの小数点以下を切り捨てた値を出力してください。

制約

• 2 \leq N \leq 100000
• 1 \leq A_i,B_i \leq N (1 \leq i \leq N - 1)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N - 1)
• どのアトラクションからどのアトラクションへも、いくつかの道を通ることで移動することができる
• 入力はすべて整数

入力例 1

3
1 2 3
2 3 6

出力例 1

4
6
6

アトラクション 1 について考えます。

アトラクション 1 からアトラクション 2 に移動する場合、通る道の「楽しさ」の平均値は 3 です。

一方、アトラクション 1 からアトラクション 3 に移動する場合、通る道の「楽しさ」の平均値は \frac{3+6}{2}=4.5 になります。

そのため、 1 行目にはこれらの最大値である 4.5 の小数点以下を切り捨てた値である 4 を出力してください。