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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> pp;

const int N = 101;
set<pii> G[N];

int n, m, p[N];

bool check(ll m) {
    priority_queue<pp> pq;
    unordered_map<int, int> maxl[N];

    pq.push({{p[n], m}, n});
    maxl[n][m] = p[n];

    while (!pq.empty()) {
        pair<pii, int> x = pq.top(); pq.pop();
        int v = x.second;
        pii intv = {x.first.second, x.first.first};
        if (v == 1 && intv.first <= 1 && 1 <= intv.second) return true;

        for (auto u : G[v]) {
            pii nintv = {(intv.first + u.first-1)/u.first, min(intv.second / u.first, p[u.second])};
            if (nintv.first > nintv.second) continue;
            if (nintv.second < 1) continue;
            if (maxl[u.second][nintv.first] >= nintv.second) continue;
            maxl[u.second][nintv.first] = nintv.second;
            pq.push({{nintv.second, nintv.first}, u.second});

            if (u.second == 1 && nintv.first <= 1 && 1 <= nintv.second) return true;
        }
    } return false;
}

void solve() {
    cin>>n>>m;
    for (int i=1; i<=n; ++i) cin>>p[i];

    for (int i=1; i<=m; ++i) {
        int a, b, w; cin>>a>>b>>w;
        G[b].insert({w, a});
    }

    int l=1, r=p[n], ans=-1;
    while (l <= r) {
        ll m=(l+r)/2;
        if (check(m)) {
            ans = m;
            l = m+1;
        } else {
            r = m-1;
        }
    } cout<<ans<<"\n";

    for (int i=0; i<=n; ++i) G[i].clear();
}

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    int t=1; cin>>t;
    while (t--) solve();
}