题目描述

学校举行跳蚤市场，有交换礼物的环节。礼物从$\red{1}$到$\red{N}$编号。小夏想要得到编号为$\red{1}$的礼物。 获取礼 物

有两种方式：

$\red{1,}$您可以直接购买礼物，第 $\red{i }$个礼物花费$\red{c_i}$钱。

$\red{2,}$您可以选择交换礼物，该活动支持$\red{M}$种交换方式：两个特定的不同礼物，可以换取一个指定礼 物。

帮助小夏花最少的钱获得第$\red{1}$号礼物。

输入格式

第一行一个数$\red{T，}$表示 $\red{T}$组数据。

每组数据第一行两个数： $\red{N}$和$\red{M }$。

接下来一行$\red{N}$个数，表示 $\red{N}$件物品的价格；

接下来 $\red{M，}$每行三个数，$\red{T_i,U_i}$和$\red{V_i ，}$表示可以使用礼物 $\red{U_i}$和$\red{V_i }$交换得到$\red{T_i }$。

输出格式

每组数据输出一个数，表示获得礼物$\red{1}$的最小费用。

样例

输入样例

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

输出样例

2
2

提示

对于$\red{30\%}$的数据，$\red{M=N-1 ，}$礼物之间恰好形成一棵树的形式；

对于 $\red{40\%}$的数据，保证礼物之间的依赖关系，不会形成环；

对于$\red{100\% }$的数据， $\red{N<=20000，}$$\red{M<=100000 ，}$$\red{T<=10 }$。