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
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<(int)b;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define PB push_back
#define EB emplace_back
#define FI first
#define SE second
#define umap unordered_map
#define uset unordered_set
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define vpii vector<pii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ALL(X) (X).begin(),(X).end()
#ifndef DEBUG
#define endl (char)10
#endif
using namespace std;
using ll = long long;
using ld = long double;

template <class T>
istream& operator>> (istream& is, vector<T>& vec){
    FOR(i,0,vec.size()) is >> vec[i];
    return is;
}
template <class T>
ostream& operator<< (ostream& os, vector<T>& vec){
    for(auto& t : vec) os << t << " ";
    return os;
}
template<class T, class U>
ostream& operator<< (ostream& os, const pair<T, U>& p){
    os << p.FI << " " << p.SE;
    return os;
}
template<class T, class U>
istream& operator>> (istream& is, pair<T, U>& p){
    is >> p.FI >> p.SE;
    return is;
}

bool is_solvable(vi& P, vector<vpii>& V) {
    priority_queue<pair<int, int>> Q;
    Q.emplace(-1, 0);
    vi dist(V.size(), INT_MAX);
    dist[0] = 1;
    while(!Q.empty()) {
        auto [d, v] = Q.top();
        Q.pop();
        d *= -1;
        if(d != dist[v]) continue;
        if (v == P.size() - 1) return true;
        for(auto& [u, x] : V[v]) {
            ll nd = d;
            nd *= x;
            if(nd <= P[u] && nd < dist[u]) {
                dist[u] = nd;
                Q.emplace(-nd, u);
            }
        }
    }
    return false;
}

void st() {
    int n, m;
    cin >> n >> m;
    vi P(n);
    cin >> P;
    vector<vpii> V(n), V2(n);
    FOR(i,0,m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        V2[a].EB(b, c);
        V[b].EB(a, c);
    }
    if(!is_solvable(P, V2)) {
        cout << -1 << endl;
        return;
    }
    int ans = -1;
    priority_queue<tuple<int, int, int, int>> Q;
    Q.emplace(P.back(), P.back(),1, n - 1);
    vector<set<pii>> seen(n);
    seen.back().emplace(P.back(), 1);
    while(!Q.empty()) {
        auto [tp, p, mul, v] = Q.top();
        Q.pop();
        if(tp <= ans) continue;
        if(v == 0) ans = max(ans, mul);
        for (auto& [u, x] : V[v]) {
            if(x <= p) {
                int np = min(p / x, P[u]);
                int nm = mul * x;
                if (!seen[u].count(make_pair(np, nm))) {
                    int ntp = np * nm;
                    seen[u].emplace(np, nm);
                    Q.emplace(ntp, np, nm, u);
                }
            }
        }
    }
    cout << ans << endl;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    FOR(i,0,t){
        //cout << "Case #" << i + 1 <<": ";
        st();
    }
}