题目描述

Bajtazar 是重金属乐队「Algosia in Antichains」的主唱，他正在为 Bajtoszyce 的演唱会做准备。除了练好粉丝喜爱的歌曲，调试音响设备也同样重要。

音响系统包含 $n$ 个路由器和 $m$ 个放大器。麦克风连着 $1$ 号路由器，扬声器接在 $n$ 号路由器上。每台放大器连接两个路由器（输入和输出），并有放大系数 $w_{i}$。每个路由器还有最大流量限制 $p_{i}$。

麦克风信号初始强度为 $1$。Bajtazar 可以自由配置信号路径，通过任意一串由放大器连接的路由器传递信号。每经过一个放大器，信号强度乘以该放大器的系数。如果某时刻信号强度超过当前路由器的流量限制，就会烧毁路由器，这是 Bajtazar 绝不想看到的。

信号可以多次经过同一路由器或放大器。Bajtazar 希望将信号传到扬声器，获得最大放大效果，同时不超出任何路由器的流量限制。请你帮他实现这个目标。

输入格式

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

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

第二行包含 $n$ 个整数 $p_{1}, p_{2}, \ldots, p_{n}$ $(1 \leq p_{i} \leq 10^{9})$，表示各路由器的最大流量。

接下来的 $m$ 行描述放大器，每行包含三个整数 $a_{i}, b_{i}, w_{i}$ $(1 \leq a_{i}, b_{i} \leq n, 1 \leq w_{i} \leq 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

在第一个音响系统中，最优配置按以下路径传输信号：

$$\begin{aligned} 1 & \rightarrow 1 (\text{信号强度为 } 2) \rightarrow 2 (\text{信号强度为 } 2 \cdot 3 = 6) \rightarrow 1 (\text{信号强度为 } 6 \cdot 37 = 222) \\ & \rightarrow 2 (\text{信号强度为 } 222 \cdot 3 = 666) \end{aligned} $$

在第二个音响系统中，最优方案为：

$$\begin{aligned} 1 & \rightarrow 1 (\text{信号强度为 } 2) \rightarrow 1 (\text{信号强度为 } 2 \cdot 2 = 4) \rightarrow 1 (\text{信号强度为 } 4 \cdot 2 = 8) \\ & \rightarrow 2 (\text{信号强度为 } 8 \cdot 1 = 8) \rightarrow 2 (\text{信号强度为 } 8 \cdot 3 = 24) \rightarrow 2 (\text{信号强度为 } 24 \cdot 3 = 72) \\ & \rightarrow 2 (\text{信号强度为 } 72 \cdot 3 = 216) \rightarrow 3 (\text{信号强度为 } 216 \cdot 1 = 216) \\ & \rightarrow 3 (\text{信号强度为 } 216 \cdot 5 = 1080) \end{aligned} $$

在第三个音响系统中：

$$1 \rightarrow 1 (\text{信号强度为 } 2) \rightarrow 1 (\text{信号强度为 } 2 \cdot 2 = 4) \rightarrow 2 (\text{信号强度为 } 4 \cdot 1 = 4) $$

在第四个音响系统中，使用放大器会导致信号强度达到 $1000000000$，超过 $2$ 号路由器的流量限制。因此，无法传递任何强度的信号。