bobo 居住的国家里，个人火箭非常流行。这个国家由 $n$ 个城市组成，编号为 $1, 2, \dots, n$。

城市之间通过双向道路连接，且任意两个城市之间有且仅有一条路径。

bobo 的国家里有 $m$ 个推销员。第 $i$ 个推销员在城市 $a_i$ 和 $b_i$ 之间的路径上旅行，并销售 $c_i$ 枚火箭。

由于火箭质量不是很高，第 $i$ 个城市最多只能购买 $w_i$ 枚火箭。

现在 bobo 想知道，在推销员们做出最大努力的情况下（即销售数量最大化），总共能卖出多少枚火箭。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n, m \le 10000$)。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($0 \le w_i \le 100000$)。

接下来的 $(n - 1)$ 行，每行包含两个整数 $u_i, v_i$，表示城市 $u_i$ 和 $v_i$ 之间有一条道路 ($1 \le u_i, v_i \le n$)。

最后 $m$ 行，每行包含 3 个整数 $a_i, b_i, c_i$ ($1 \le a_i, b_i \le n, 0 \le c_i \le 100000$)。

输出格式

输出一个整数，表示能卖出的火箭的最大数量。

样例

输入 1

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

输出 1

5