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
#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define _DEBUG
#ifdef _DEBUG
template<typename T1, typename T2> auto& operator<<(ostream& o, pair<T1, T2> a) { return o << "(" << a.first << ", " << a.second << ")"; }
template<typename T, typename OS> auto& operator<<(OS& o, T a) { o << "{"; for (auto b : a) o << b << ", "; return o << "}"; }
#define dbg(x...) cerr << "[" #x "]: ", [](auto... args) { ((cerr << args << ", "),...) << "\n"; }(x)
#else
#define dbg(...)
#endif

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

template<class T>
using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
using vi = vector<int>;

ll n, m, s;
vector<ll> d;
vector<set<pll>> adj;// {u, k}
vector<bool> visited, is_end, abandoned;
vector<map<ll, vector<pll>>> g; // g[v][k][u, max_d];

void dfs1(ll v) {
    visited = vector<bool>(n, false);

    std::priority_queue<pll> pq; //max_d, v;
    pq.emplace(d[v], v);
    while(!pq.empty()) {
        auto [max_d, p] = pq.top(); pq.pop();

        if(visited[p]) continue;
        if(v == 0) is_end[p] = true;
        visited[p] = true;

        for(auto [u, k] : adj[p]) {
            ll u_d = min(max_d, d[u]);
            if(k==1) {
                pq.emplace(u_d, u);
            }
            if(k != 1 || u == n-1) {
                g[u][k].emplace_back(v, max_d);
            }
        }
    }
}

set<tuple<ll,ll,ll>> states;
ll mx = -1;
void dfs2(ll v, ll max_d, ll cur) {
    if(states.count({v, max_d, cur})) return;
    states.emplace(v, max_d, cur);
    if(max_d < 1 || max_d*cur < mx) return;
    if(is_end[v]) mx = max(mx, cur);
    for(auto [k, xd] : g[v]) {
        if(k == 1 && max_d != d[n-1]) continue;
        if(max_d/k < 1) break;
        for(auto [u, ud] : xd) {
            dfs2(u, min(max_d/k, ud), cur*k);
        }
    }
}

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

    ll t;
    cin >> t;

    while (t--) {
        cin >> n >> m;
        mx = -1;
        d = vector<ll>(n);
        adj = vector<set<pll>>(n, set<pll>());
        is_end = vector<bool>(n, false);
        abandoned = vector<bool>(n, true);
        g = vector<map<ll, vector<pll>>>(n, map<ll, vector<pll>>());
        for(ll i = 0 ; i < n ; ++i) {
            cin >> d[i];
        }
        for(ll i = 0 ; i < m ; ++i) {
            ll a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            if(c > 1) abandoned[b] = false;
            adj[a].emplace(b, c);
        }
        for(ll i = 0 ; i < n ; ++i) {
            if(!abandoned[i] || i == 0 || i == n-1)
                dfs1(i);
        }
        dfs2(n-1, d[n-1], 1);
        cout << mx << '\n';
    }


    return 0;
}