#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<long long> p(n + 1);
        for (int i = 1; i <= n; ++i) cin >> p[i];
 
        vector<vector<pair<int,long long>>> g(n + 1);
        for (int i = 0; i < m; ++i) {
            int a, b;
            long long w;
            cin >> a >> b >> w;
            g[a].push_back({b, w});
        }
 
        vector<unordered_set<long long>> seen(n + 1);
        queue<pair<int,long long>> q;
 
        long long ans = -1;
 
        if (1 <= p[1]) {
            q.push({1, 1});
            seen[1].insert(1);
        }
 
        while (!q.empty()) {
            auto [u, val] = q.front();
            q.pop();
 
            if (u == n) ans = max(ans, val);
 
            for (auto [v, w] : g[u]) {
                // kiểm tra val * w <= p[v] mà không bị tràn
                if (val > p[v] / w) continue;
                long long newVal = val * w;
                if (!seen[v].count(newVal)) {
                    seen[v].insert(newVal);
                    q.push({v, newVal});
                }
            }
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0cik7CgogICAgaW50IFQ7CiAgICBpZiAoIShjaW4gPj4gVCkpIHJldHVybiAwOwogICAgd2hpbGUgKFQtLSkgewogICAgICAgIGludCBuLCBtOwogICAgICAgIGNpbiA+PiBuID4+IG07CiAgICAgICAgdmVjdG9yPGxvbmcgbG9uZz4gcChuICsgMSk7CiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSBjaW4gPj4gcFtpXTsKCiAgICAgICAgdmVjdG9yPHZlY3RvcjxwYWlyPGludCxsb25nIGxvbmc+Pj4gZyhuICsgMSk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyArK2kpIHsKICAgICAgICAgICAgaW50IGEsIGI7CiAgICAgICAgICAgIGxvbmcgbG9uZyB3OwogICAgICAgICAgICBjaW4gPj4gYSA+PiBiID4+IHc7CiAgICAgICAgICAgIGdbYV0ucHVzaF9iYWNrKHtiLCB3fSk7CiAgICAgICAgfQoKICAgICAgICB2ZWN0b3I8dW5vcmRlcmVkX3NldDxsb25nIGxvbmc+PiBzZWVuKG4gKyAxKTsKICAgICAgICBxdWV1ZTxwYWlyPGludCxsb25nIGxvbmc+PiBxOwoKICAgICAgICBsb25nIGxvbmcgYW5zID0gLTE7CgogICAgICAgIGlmICgxIDw9IHBbMV0pIHsKICAgICAgICAgICAgcS5wdXNoKHsxLCAxfSk7CiAgICAgICAgICAgIHNlZW5bMV0uaW5zZXJ0KDEpOwogICAgICAgIH0KCiAgICAgICAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgICAgICAgICAgYXV0byBbdSwgdmFsXSA9IHEuZnJvbnQoKTsKICAgICAgICAgICAgcS5wb3AoKTsKCiAgICAgICAgICAgIGlmICh1ID09IG4pIGFucyA9IG1heChhbnMsIHZhbCk7CgogICAgICAgICAgICBmb3IgKGF1dG8gW3YsIHddIDogZ1t1XSkgewogICAgICAgICAgICAgICAgLy8ga2nhu4NtIHRyYSB2YWwgKiB3IDw9IHBbdl0gbcOgIGtow7RuZyBi4buLIHRyw6BuCiAgICAgICAgICAgICAgICBpZiAodmFsID4gcFt2XSAvIHcpIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgbG9uZyBsb25nIG5ld1ZhbCA9IHZhbCAqIHc7CiAgICAgICAgICAgICAgICBpZiAoIXNlZW5bdl0uY291bnQobmV3VmFsKSkgewogICAgICAgICAgICAgICAgICAgIHNlZW5bdl0uaW5zZXJ0KG5ld1ZhbCk7CiAgICAgICAgICAgICAgICAgICAgcS5wdXNoKHt2LCBuZXdWYWx9KTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgY291dCA8PCBhbnMgPDwgIlxuIjsKICAgIH0KCiAgICByZXR1cm4gMDsKfQ==

NAoyIDMKMjUgMTAwCjEgMSAyCjEgMiAzCjIgMSAxMAozIDUKNTAgODAgMTEwCjEgMSAyCjIgMiAzCjIgMyAxCjEgMiAxCjMgMyA1CjIgMgo0IDQKMSAxIDIKMSAyIDEKMiAxCjEwIDEwCjEgMiA5OTk5OTkK

4
2 3
25 100
1 1 2
1 2 3
2 1 10
3 5
50 80 110
1 1 2
2 2 3
2 3 1
1 2 1
3 3 5
2 2
4 4
1 1 2
1 2 1
2 1
10 10
1 2 999999