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

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
    o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
    return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
    ((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

const int SQ = 35'000;

vector<vi> getLewa(vector<vector<pii>> &G, vi &p) {
    int n = SZ(G);
    vector<vi> vis(n, vi(SQ));
    queue<pii> q;
    vis[0][1] = 1;
    q.push({0, 1});
    while(!q.empty()) {
        auto [v, moc] = q.front();
        q.pop();
        for(auto &[u, boost]: G[v]) {
            ll nowa = ll(moc) * boost;
            if(nowa < SQ && !vis[u][nowa] && nowa <= p[u]) {
                vis[u][nowa] = 1;
                q.push({u, nowa});
            } 
        }
    }
    vector<vi> good(n);
    FOR(i, 0, n) FOR(j, 0, SQ) if(vis[i][j]) good[i].pb(j);
    return good;
}

vector<vi> getPrawa(vector<vector<pii>> &G, vi &p) {
    int n = SZ(G);
    vector<vector<pii>> GR(n);
    FOR(v, 0, n) for(auto &[u, boost]: G[v]) GR[u].pb({v, boost});
    vector<vi> dist(n, vi(SQ));
    priority_queue<tuple<int, int, int>> q;
    dist[n - 1][1] = p[n - 1];
    q.push({p[n - 1], n - 1, 1});
    while(!q.empty()) {
        auto [lim, v, moc] = q.top();
        q.pop();
        for(auto &[u, boost]: GR[v]) {
            int nlim = min(lim / boost, p[u]);
            ll nmoc = ll(moc) * boost;
            if(nmoc < SQ && dist[u][nmoc] < nlim) {
                dist[u][nmoc] = nlim;
                q.push({nlim, u, nmoc});
            }
        }
    }
    return dist;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> G(n);
    vi p(n);
    for(auto &x: p) cin >> x;
    FOR(i, 0, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        G[a].pb({b, c});
    }
    auto lewa = getLewa(G, p);
    auto prawa = getPrawa(G, p);
    int ans = (n == 1 ? 1 : -1);
    FOR(v, 0, n) for(auto &[u, moc]: G[v]) {
        FOR(boost, 1, SQ) {
            int bound = prawa[u][boost] / moc;
            auto it = upper_bound(all(lewa[v]), bound);
            if(it == lewa[v].begin()) continue;
            int zlewo = *prev(it);
            ans = max(ans, zlewo * moc * boost);
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    cin >> tt;
    FOR(te, 0, tt) solve();
    return 0;
}