P11927 [PA 2025] 重金属 / Heavy Metal

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$。

### 样例解释 $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$。