Bajtazar 是一支重金属乐队 Algosia in Antichains 的主唱，正在为在 Bajtoszyce 的演唱会做准备。除了准备观众最喜欢的歌曲之外，音响设备的准备同样重要。

音响系统由 $n$ 个路由器和 $m$ 个放大器组成。麦克风连接到编号为 $1$ 的路由器，扬声器连接到编号为 $n$ 的路由器。每个放大器连接两个路由器（输入和输出），并具有增益系数 $w_i$。每个路由器还有一个最大吞吐量 $p_i$。

来自麦克风的信号初始功率为 $1$。Bajtazar 可以配置系统，使信号通过由放大器连接的任意一条路由器路径进行传输。信号每通过一个放大器，其功率会乘以该放大器的增益系数。如果在任何时刻，当前传输的信号功率超过了所经过路由器的吞吐量，那么该路由器就会被烧毁，这是 Bajtazar 绝对要避免的。

信号可以任意多次经过同一个路由器或放大器。Bajtazar 希望最终将信号传输到扬声器，在不超过任何路由器吞吐量的前提下，使信号的增益尽可能大。请帮助他实现这一目标。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 100$），表示 Bajtazar 拥有的音响系统数量。接下来是 $T$ 个音响系统的描述。

每个系统描述的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m$），分别表示路由器数量和放大器数量。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le 10^9$），表示各个路由器的吞吐量。

接下来的 $m$ 行描述放大器，第 $i$ 行包含三个整数 $a_i, b_i, w_i$（$1 \le a_i, b_i \le n,\ 1 \le w_i \le 10^9$），分别表示第 $i$ 个放大器的输入路由器、输出路由器以及增益系数。

所有测试中 $n$ 的总和不超过 $100$，$m$ 的总和不超过 $200$。

输出格式

输出 $T$ 行；第 $i$ 行应包含一个整数，表示第 $i$ 个音响系统中信号可能达到的最大增益。如果无法使用该系统将信号传输到扬声器，则输出 $-1$。

样例数据

对于以下输入：

4
2 3
250 1000
1 1 2
1 2 3
2 1 37
3 5
500 800 1100
1 1 2
1 2 1
2 2 3
2 3 1
3 3 5
2 2
4 4
1 1 2
1 2 1
2 1
10 10
1 2 1000000000

正确的输出为：

666
1080
4
-1

样例说明

在第一个音响系统中，最优配置的信号传输过程如下：

$1 \rightarrow 1$（功率 $2$）$\rightarrow 2$（功率 $2 \cdot 3 = 6$）$\rightarrow 1$（功率 $6 \cdot 37 = 222$） $\rightarrow 2$（功率 $222 \cdot 3 = 666$）

在第二个系统中，最优解为：

$1 \rightarrow 1$（功率 $2$）$\rightarrow 1$（功率 $2 \cdot 2 = 4$）$\rightarrow 1$（功率 $4 \cdot 2 = 8$） $\rightarrow 2$（功率 $8 \cdot 1 = 8$）$\rightarrow 2$（功率 $8 \cdot 3 = 24$）$\rightarrow 2$（功率 $24 \cdot 3 = 72$） $\rightarrow 2$（功率 $72 \cdot 3 = 216$）$\rightarrow 3$（功率 $216 \cdot 1 = 216$） $\rightarrow 3$（功率 $216 \cdot 5 = 1080$）

在第三个系统中：

$1 \rightarrow 1$（功率 $2$）$\rightarrow 1$（功率 $2 \cdot 2 = 4$）$\rightarrow 2$（功率 $4 \cdot 1 = 4$）

在第四个系统中，通过放大器传输信号会导致信号功率达到 $1\,000\,000\,000$，超过了编号为 $2$ 的路由器的吞吐量。因此无法传输任何功率的信号。