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