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
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;
#define f first
#define s second
const int N = 1e2 + 5;
const int N2 = 2e6 + 5;

int n, m;
int w[N];
int lst;
priority_queue<int> Q;
int a, b, c;
vector<pii> adj[N];
vector<int> vec;
vector<int> vec2;
int dp[N2][N];
priority_queue<pii> Q2;

bool vis[N];
int id[N];
// vector<int> adj2[N];
// vector<int> adj2r[N];
// vector<int> adjs[N];
// vector<int> topo;
// vector<int> scc[N];
// int sccn[N];
// int dp2[N];
int sccs;

// void dfs(int v){
//     vis[v] = 1;
//     for(auto u : adj2[v]){
//         if(vis[u]) continue;
//         dfs(u);
//     }
//     topo.push_back(v);
// }

// void dfs2(int v){
//     vis[v] = 1;
//     scc[sccs].push_back(v);
//     sccn[v] = sccs;
//     for(auto u : adj2r[v]){
//         if(vis[u]) continue;
//         dfs2(u);
//     }
// }

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int tt;
    cin >> tt;
    while(tt--){
        cin >> n >> m;

        while(Q.size()) Q.pop();
        vec.clear();
        vec2.clear();
        // topo.clear();

        for(int i=0;i<n;i++){
            // adjs[i].clear();
            // adj2[i].clear();
            // adj2r[i].clear();
            //scc[i].clear();
            adj[i].clear();
            cin >> w[i];
            Q.push(w[i]);
        }

        for(int i=0;i<m;i++){
            cin >> a >> b >> c;
            a--; b--;
            adj[a].emplace_back(b,c);
            // else{
            //     adj2[a].push_back(b);
            //     adj2r[b].push_back(a);

            // }
            if(c>1) vec2.push_back(c);
        }

        sort(vec2.begin(),vec2.end());
        lst = -1;
        while(Q.size()){
            int v = Q.top(); Q.pop();
            if(lst == v) continue;
            vec.push_back(v);
            for(auto u : vec2){
                int l = v/u;
                if(l > 1) Q.push(l);
            }
            lst = v;
        }

        if(vec.back() != 1) vec.push_back(1);
        reverse(vec.begin(),vec.end());

        for(int i=0;i<(int)vec.size();i++){
            for(int j=0;j<n;j++){
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 1;

        for(int i=0;i<(int)vec.size();i++){
            while(Q2.size()) Q2.pop();
            for(int j=0;j<n;j++){
                Q2.emplace(dp[i][j], j);
            }
            
            while(Q2.size()){
                pii p = Q2.top(); Q2.pop();
                if(dp[i][p.s] != p.f) continue;
                for(auto& [u, wg] : adj[p.s]){
                    long long k = 1LL * p.f * wg;
                    if(k > w[u]) continue;
                    int idx = lower_bound(vec.begin(),vec.end(),k) - vec.begin();
                    if(idx == i && k > dp[i][u]){
                        Q2.emplace(k, u);
                    }
                    dp[idx][u] = max(dp[idx][u], (int)k);
                }
            }
        }

        // for(int i=0;i<(int)vec.size();i++){
        //     for(int j=0;j<n;j++){
        //         cout << vec[i] << " " << j << " " << dp[i][j] << "\n";
        //     }
        // }

        int mx = 0;
        for(int i=0;i<(int)vec.size();i++){
            mx = max(mx, dp[i][n-1]);
        }

        cout << (mx == 0 ? -1 : mx) << "\n";

        cerr << tt << "\n";
    }

    return 0;
}