首先看到这个乘法，那么大概率就和值域 V 有关了，但是“最多只经过 O(\log V) 条边权不为 1 的边”貌似没有什么用。观察到 n 很小，小到 O(n\sqrt V) 都是可以接受的。那么可以考虑把路径分成两段边权不超过 \sqrt V 的部分，分别处理，最后再枚举中间连接的边统计答案，这就有了一个 meet-in-middle 的壳子。
考虑统计的是 u\rightarrow v 这条边，边权为 w。那么应该需要维护两个信息：f_{i,j} 表示是否有一条 1\rightarrow i 的路径边权积为 j；g_{i,j} 表示所有 i\rightarrow n 的边权积为 j 的路径中，可以接受的 1\sim i 的最大边权积。求出 f 和 g 只有，对 f_u 和 g_v 双指针一下就可以更新答案了。
时间复杂度为 $O(n\sqrt V\log m)$，平衡一下可以做到 $O(n\sqrt{V\log m})$，但是我懒。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 105
#define MAXK 32005
int t, n, m; int p[MAXN];
bool f[MAXN][MAXK], vis[MAXN][MAXK]; int h[MAXN][MAXK];
vector<pair<int, int>> e[MAXN], g[MAXN];
struct Node{int u, st, d; bool operator<(Node b)const{return d < b.d;}};
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for (cin >> t; t; --t){
cin >> n >> m; for (int i(1); i<=n; ++i) cin >> p[i];
for (int u, v, w; m; --m) cin >> u >> v >> w, e[u].push_back({v, w}), g[v].push_back({u, w});
queue<pair<int, int>> que; que.push({1, 1}); f[1][1] = 1;
while (que.size()){
int u(que.front().first), st(que.front().second); que.pop();
for (auto i: e[u]){
int v(i.first), w(i.second); if (w*st<=min(MAXK-1ll, p[v]) && !f[v][w*st]) f[v][w*st] = 1, que.push({v, w*st});
}
}
priority_queue<Node> pq; pq.push({n, 1, h[n][1]=p[n]});
while (pq.size()){
int u(pq.top().u), st(pq.top().st); pq.pop(); if (vis[u][st]) continue; vis[u][st] = 1;
for (auto i: g[u]){
int v(i.first), w(i.second);
if (w*st < MAXK && min(p[v], h[u][st]/w) > h[v][st*w]){
pq.push({v, st*w, h[v][st*w]=min(p[v], h[u][st]/w)});
}
}
}
int ans(-1);
for (int i(1); i<=n; ++i) for (auto j: e[i]){
int v(j.first), w(j.second);
for (int x(1), y(MAXK-1); x<MAXK; ++x){
for (; y && h[v][y] < w*x; --y); if (y && f[i][x]) ans = max(ans, y*w*x);
}
}
cout << (n == 1 && ans == -1 ? 1 : ans) << '\n';
for (int i(1); i<=n; ++i){
for (int j(1); j<MAXK; ++j) vis[i][j] = f[i][j] = h[i][j] = 0;
e[i].clear(); e[i].shrink_to_fit(); g[i].clear(); g[i].shrink_to_fit();
}
}
return 0;
}
```