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
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;

#define LOCAL false

/*
xk <= sqrt(10^9)
dist1[v] = {x1, x2, ...} <=> moge dojsc z 1 do v konczac z iloczynem x1, x2, ... niczego nie psujac
dist2[v] = {(x1, t1), (x2, t2)} <=> dla kazdej pary moge dojsc z v do konca konczac z iloczynem x w taki sposob ze t to 
                                    najwieksza liczba, ze sie jak pomnoze wszystko przez t to sie nic nie popsuje
*/

const int TRES = 31623+420;

const int MAXV = 107;
int V, E;

vector<pii> graph[MAXV], graphT[MAXV];
int cap[MAXV];
vector<tuple<int, int, int>> edges;

set<int> dist1[MAXV];
map<int, int> dist2[MAXV];

void dfs(int v, ll prod) {
    dist1[v].insert(prod);
    for (auto [to, x]: graph[v]) {
        ll prod2 = prod*x;
        if (prod2 <= min(TRES, cap[to]) && !dist1[to].count(prod2)) dfs(to, prod2);
    }
}

void solve() {
    cin >> V >> E;
    rep1(v, V) cin >> cap[v];
    int v1, v2, x;
    rep(i, E) {
        cin >> v1 >> v2 >> x;
        graph[v1].push_back({v2, x});
        graphT[v2].push_back({v1, x});
        edges.push_back({v1, v2, x});
    }

    dfs(1, 1);

    priority_queue<pair<pll, int>> Q;
    Q.push({ {cap[V], 1LL}, V });
    while (!Q.empty()) {
        auto [dat, v] = Q.top();
        auto [t, prod] = dat;
        Q.pop();
        if (dist2[v].find(prod) == dist2[v].end()) {
            dist2[v][prod] = t;
            for (auto [to, x]: graphT[v]) {
                ll prod2 = prod*x;
                if (prod2 <= TRES && x <= t && dist2[to].find(prod2) == dist2[to].end()) {
                    Q.push({{min((ll)cap[to], t/x), prod2}, to});
                }
            }
        }
    }

    int ans = (V!=1 ? -1 : 1);
    for (auto [v1, v2, x]: edges) {
        vector<pii> dist2vec(all(dist2[v2]));
        for (auto& [prod, t]: dist2vec) swap(prod, t);
        sort(all(dist2vec), greater{});
        int d2idx = 0;
        int bestd2 = -1;
        for (auto it = dist1[v1].rbegin(); it != dist1[v1].rend(); it++) {
            ll prod2 = (ll)(*it)*x;
            while (d2idx < dist2vec.size() && dist2vec[d2idx].first >= prod2) {
                bestd2 = max(bestd2, dist2vec[d2idx].second);
                d2idx++;
            }
            ans = max((ll)ans, prod2*bestd2);
        }
    }
    cout << ans << "\n";

    edges.clear();
    rep1(v, V) {
        graph[v].clear();
        graphT[v].clear();
        dist1[v].clear();
        dist2[v].clear();
    }
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (LOCAL) {
        ignore=freopen("io/in", "r", stdin);
        ignore=freopen("io/out", "w", stdout);
    }

    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}