Bessie 為全國乳牛籌辦一年一度的乳牛大聚會，當然想選最方便的地點。

每頭牛住在 $N$（$1 \le N \le 100,000$）個牛棚之一，編號 $1..N$。$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$）頭牛。

Bessie 要使便利最大，即不便最小。選牛棚 $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