题目背景

PA 2025 R5B.

题目描述

扩音系统由 $n$ 个路由器和 $m$ 个放大器组成。麦克风连接到第 $1$ 号路由器，扬声器连接到第 $n$ 号路由器。

每个放大器连接两个路由器（输入和输出），增益系数为 $w_i$。路由器的最大带宽为 $p_i$。

麦克风的信号功率为 $1$。配置系统，使信号在放大器、路由器中传输。信号经过放大器后，功率会乘以该放大器的增益系数，但是为了避免烧毁，通过路由器的信号功率必须不大于 $p_i$。

信号可以多次通过同一路由器或放大器。最终将信号传输到扬声器（到达 $n$ 号路由器），在路由器不烧毁的前提下，最大化信号的功率。求出可能的最大功率。

输入格式

本题单个测试点内含有多组测试数据。

第一行，正整数 $T$，表示测试数据组数。接下来依次描述 $T$ 组数据：

每组数据第一行，两个正整数 $n,m$。

每组数据第二行，$n$ 个正整数 $p_1,p_2,\ldots,p_n$。

每组数据接下来的 $m$ 行，每行三个正整数 $a_i,b_i,w_i$，表示放大器的输入路由器、输出路由器和增益系数。

输出格式

输出 $T$ 行，每行一个整数：

• 若能成功将信号传输到扬声器，输出可能的最大增益系数；
• 否则，输出一行一个 $-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

提示

样例解释

$114(514)$ 表示，信号到达第 $114$ 个路由器时，功率为 $514$。

• 样例 $1$ 解释：

最优路径：$1(1)\to 1(1\times 2)\to 2(2\times 3)\to 1(6\times 37)\to 2(222\times 3)$。

• 样例 $2$ 解释：

最优路径：$1(1)\to 1(2)\to 1(4)\to 1(8)\to 2(8)\to 2(24)\to 2(72)\to 2(216)\to 3(216)\to 3(1080)$。

• 样例 $3$ 解释：

最优路径：$1\to 1(2)\to 1(4)\to 2(4)$。

• 样例 $4$ 解释：路由器 $2$ 一定会被烧毁，所以无法传到路由器 $2$。

数据范围

• $1\le n,\sum n\le 100$；
• $1\le m,\sum m\le 200$；
• $1\le p_i\le 10^9$；
• $1\le a_i,b_i\le n$；
• $1\le w_i\le 10^9$。