小瓦夏正在玩一款名为“矮人塔”（Dwarf Tower）的新游戏。在这个游戏中，有 $n$ 种不同的物品可以装备在矮人角色身上。物品编号从 $1$ 到 $n$。瓦夏想要获得编号为 $1$ 的物品。

获得物品有两种方式： 你可以购买物品。第 $i$ 个物品的价格为 $c_i$。 你可以制作物品。游戏支持 $m$ 种制作配方。制作一个物品时，你需要消耗两种特定的不同物品，并获得另一种物品作为结果。

请帮助瓦夏计算获得编号为 $1$ 的物品所需花费的最少金额。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10\,000; 0 \le m \le 100\,000$)，分别表示不同物品的数量和制作配方的数量。

第二行包含 $n$ 个整数 $c_i$，表示物品的价格 ($0 \le c_i \le 10^9$)。

接下来的 $m$ 行描述了制作配方，每行包含三个不同的整数 $a_i, x_i, y_i$，表示物品 $a_i$ 可以通过物品 $x_i$ 和 $y_i$ 制作得到 ($1 \le a_i, x_i, y_i \le n; a_i \neq x_i; x_i \neq y_i; y_i \neq a_i$)。

输出格式

输出一个整数，表示获得物品所需花费的最少金额。

样例

样例输入 1

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

样例输出 1

2

样例输入 2

3 1
2 2 1
1 2 3

样例输出 2

2