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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll a,b,c,t,n,m;
unordered_map<ll,ll> bst[104];// najlepszy limit dla [] gdy mnozymy przez []
vector<pair<ll,ll>>g[104];//kto mnoznik
ll ile[104];//tresh



void solve(){
    cin>>n>>m;
    for(ll i=0;i<n;i++)
        cin>>ile[i+1];
    for(ll i=1;i<=n;i++)
        g[i].clear();
    for(ll i=1;i<=n;i++)
        bst[i].clear();
    for(ll i=0;i<m;i++){
        cin>>a>>b>>c;
        g[b].pb({a,c});
    }
    ll ans=-1;
    priority_queue<pair<pair<ll,ll>,ll>>pq;// treshold, mnoznik
    pq.push({{ile[n],1},n});
    while(!pq.empty()){
        auto pom=pq.top();
        pq.pop();
        if(pom.ff.ff==0 || bst[pom.ss][pom.ff.ff])continue;
        bst[pom.ss][pom.ff.ff]=pom.ff.ss;
        //cout<<pom.ff.ff<<" "<<pom.ff.ss<<" "<<pom.ss<<"\n";
        if(pom.ss==1)
            ans=max(ans,pom.ff.ss);
        for(pair<ll,ll>i : g[pom.ss]){
            pq.push({{min(pom.ff.ff/i.ss,ile[i.ff]),pom.ff.ss*i.ss},i.ff});
        }
    }
    cout<<ans<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--){
        solve();
    }




    return 0;
}