题目描述

你来到了一个奇特的商店，里面有$\red{n}$个商品，编号为$\red{1}$到$\red{n}$。你的目标是得到$\red{1}$号商品。

在这个奇特的商店里面，你可以通过两种方式获得一个商品：

$\red{1}$、直接购买该商品，购买商品$\red{i}$的花费为$\red{c_i}$；

$\red{2}$、用两件商品合成所需商品，一共给出$\red{m}$种合成方式。

请问获得$\red{1}$号商品的最小花费是多少呢？

输入格式

第一行输入两个正整数$\red{n,m}$

第二行输入$\red{n}$个整数，$\red{c_1,c_2,...,c_n}$

接下来$\red{m}$行，每行$\red{3}$个整数$\red{a_i,x_i,y_i，}$表示$\red{a}$可以由$\red{x,y}$合成得到$\red{(1<=a_i,x_i,y_i<=n}$;$\red{a_i≠}$$\red{x_i}$;$\red{x_i≠}$$\red{y_i}$;$\red{y_i≠}$$\red{a_i)}$

输出格式

输出一个整数表示答案

样例

输入样例

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

输出样例

2

提示

对于$\red{100\%}$的数据，$\red{1<=n<=100000,1<=m<=100000,1<=c_i<=10^9}$

对于$\red{40\%}$的数据， $\red{1<=n<=100,1<=m<=100}$