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
#include <bits/stdc++.h>
using namespace std;

#define ll long long


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; _++) {
        int n, m;
        cin >> n >> m;
        vector<ll> p (n+1, 0);
        for (int i = 0; i < n; i++) {
            cin >> p[i+1];
        }
        vector<vector<pair<ll, ll>>> g (n+1);
        for (int i = 0; i < m; i++) {
            ll a, b, w;
            cin >> a >> b >> w;
            g[a].push_back({b, w});
        }
        unordered_map<ll, bool> odw;
        queue<pair<ll, ll>> q;
        q.push({1, 1});
        ll maks = -1;
        while (!q.empty()) {
            auto x = q.front();
            q.pop();
            if (odw[x.second*102+x.first]) {
                continue;
            }
            odw[x.second*102+x.first] = 1;
            if (x.first == n) {
                maks = max(maks, x.second);
            }
            for (auto v : g[x.first]) {
                if (x.second*v.second  <= p[v.first]) {
                    q.push({v.first, x.second*v.second});
                }
            }
        }
        cout << maks << '\n';
    }
}