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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll LIM=107, K1=2e5+7, K2=5e3+7;
vector<pair<ll,ll>>V[LIM], S[LIM];
ll T[LIM], dp1[LIM][K1], dp2[LIM][K2], A[2*LIM], B[2*LIM], C[2*LIM], n, m;
void BFS() {
	dp1[0][1]=1;
	queue<pair<ll,ll>>q;
	q.push({0, 1});
	while(!q.empty()) {
		ll p=q.front().st, o=q.front().nd; q.pop();
		for(auto i : V[p]) if(o*i.nd<K1 && o*i.nd<=T[i.st] && !dp1[i.st][o*i.nd]) {
			dp1[i.st][o*i.nd]=1;
			q.push({i.st, o*i.nd});
		}
	}
}
void DIJ() {
	priority_queue<pair<ll,pair<ll,ll>>>q;
	q.push({T[n-1], {n-1, 1}});
	while(!q.empty()) {
		ll o=q.top().st, a=q.top().nd.st, b=q.top().nd.nd; q.pop();
		if(dp2[a][b]>=o) continue;
		dp2[a][b]=o;
		for(auto i : S[a]) if(i.nd<=o && b*i.nd<K2) q.push({min(o/i.nd, T[i.st]), {i.st, b*i.nd}});
	}
}
void solve() {
	cin >> n >> m;
	rep(i, n) {
		cin >> T[i];
		V[i].clear();
		S[i].clear();
		rep(j, K1) dp1[i][j]=0;
		rep(j, K2) dp2[i][j]=0;
	}
	rep(i, m) {
		cin >> A[i] >> B[i] >> C[i];
		--A[i]; --B[i];
		V[A[i]].pb({B[i], C[i]});
		S[B[i]].pb({A[i], C[i]});
	}
	BFS();
	DIJ();
	ll ans=-1;
	if(n==1) ans=1;
	rep(i, m) {
		vector<pair<ll,ll>>P;
		rep(j, K2) if(dp2[B[i]][j]) P.pb({dp2[B[i]][j], j});
		sort(all(P));
		for(int j=(int)P.size()-2; j>=0; --j) P[j].nd=max(P[j].nd, P[j+1].nd);
		int l=0;
		rep(j, K1) if(dp1[A[i]][j] && C[i]*j<=T[B[i]]) {
			while(l<P.size() && P[l].st<C[i]*j) ++l;
			if(l<P.size()) ans=max(ans, C[i]*j*P[l].nd);
		}
	}
	cout << ans << '\n';
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int _=1;
	cin >> _;
	while(_--) solve();
}