Bessie は全国の牛の年一度の大集会を計画し、最も便利な場所を選びたいです。

各牛は番号 $1..N$ の $N$（$1 \le N \le 100,000$）牛舎の一つに住み、$N-1$ 道で全て相互に到達できます。道 $i$ は $A_{i}$、$B_{i}$（$1 \le A_i \le N; 1 \le B_i \le N$）を結び長さ $L_{i}$（$1 \le L_{i} \le 1,000$）。$N$ 舎のどこでも開催でき、牛舎 $i$ には $C_{i}$（$0 \le C_{i} \le 1,000$）頭です。

便利を最大、つまり不便を最小にします。牛舎 $X$ の不便は全牛が $X$ まで移動する距離の合計。牛舎 $i$ から $X$ まで 20 なら $C_{i}*20$ です。最適な開催場所を求めます。

五舎の例で角括弧の頭数は様々、道の長さも異なります。3 と 4 には牛がいません。

      1     3     4     5
      @--1--@--3--@--3--@[2]
     [1]    |
            2
            |
            @[1]
            2

どの五舎も会場にでき、下表は不便です。B1 から B5 は各舎、最後は合計。

牛舎 1 に開催すると各舎の不便は：

• 牛舎 1：0、移動不要！
• 牛舎 2：3、距離 $2+1=3$ に 1 頭を掛けて 3。
• 牛舎 3：0、牛なし！
• 牛舎 4：0、牛なし！
• 牛舎 5：14、距離 $3+3+1=7$ に 2 頭を掛けて 14。

合計不便は 17。

最小は 15 で、3、4、5 のいずれでも達成します。

入力

• 1 行目：整数 $N$。
• $2..N+1$ 行目：第 $i+1$ 行に整数 $C_{i}$。
• $N+2..2N$ 行目：第 $i+N+1$ 行に整数 $A_{i}$、$B_{i}$、$L_{i}$ 三つ。

出力

• 1 行目：可能な最小の不便。

入出力例

入力 1

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

出力 1

15

問題作成者：Jeffrey Wang、ある大会より、2010