1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>

#define llong long long
#define ldouble long double
#define uint unsigned int
#define ulong unsigned long long

using namespace std;

struct edge {
    int v, w;
};

int n, m;
int best;
vector<unordered_set<int>> visited;
vector<vector<edge>> G;
vector<int> p;

void dfs(int u, int pow) {
    if (u == n - 1) {
        best = max(best, pow);
    }

    for (auto[v, w] : G[u]) {
        if (1ll * pow * w > p[v]) continue;
        int new_pow = pow * w;
        if (visited[v].find(new_pow) != visited[v].end()) continue;
        visited[v].insert(new_pow);
        dfs(v, new_pow);
    }
}

void solve() {
    cin >> n >> m;
    p.resize(n);
    G.assign(n, vector<edge>());
    for (int i = 0; i < n; i++) cin >> p[i];

    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({v, w});
    }

    visited.assign(n, unordered_set<int>());
    visited[0].insert(1);
    best = 0;
    dfs(0, 1);
    
    cout << (best == 0 ? -1 : best) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t; cin >> t;

    while (t--) solve();

    return 0;
}