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>
#define ll long long
using namespace std;

ll bfs(vector<pair<int, ll>> graf[], vector<ll> przepust, int n){
    vector<unordered_set<ll>> dp(n + 1);
    queue<pair<int, ll>> q;
    dp[1].insert(1);
    q.push({1, 1});
    while(!q.empty()){
        pair<int, ll> w = q.front();
        q.pop();
        for(auto u : graf[w.first]){
            ll akt = w.second * u.second;
            if(akt <= przepust[u.first]){
                if(!dp[u.first].count(akt)){
                    dp[u.first].insert(akt);
                    q.push({u.first, akt});
                }
            }
        }
    }
    if(dp[n].empty()) return -1LL;
    ll maxi = 0;
    for(auto x : dp[n]) maxi = max(maxi, x);
    return maxi;
}
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        vector<ll> przepust(n + 1, 0);
        for(int i = 1; i <= n; i++) cin >> przepust[i];
        vector<pair<int, ll>> graf[n + 1];
        for(int i = 0; i < m; i++){
            ll a, b, w;
            cin >> a >> b >> w;
            graf[a].push_back({b, w});
        }
        cout << bfs(graf, przepust, n) << '\n';
    }
}