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

using namespace std;
typedef long long ll;
const int MAXN=100;

ll read()
{
	bool start=0, neg=0;
	ll num=0;
	char z;
	while(true){
		z = getchar();
		if((z < '0' || z > '9') && z != '-' && !start){
			continue;
		}
		if((z < '0' || z > '9') && z != '-' && start){
			break;
		}
		if(start) num*=10;
		start=1;
		if(z=='-') neg=1;
		else num += z-'0';
	}
	if(neg) return -1*num;
	else return num;
}

int n;
ll P[MAXN+5];
vector<pair<int,ll>> adj[MAXN+5];
unordered_map<ll, bool> M[MAXN+5];

ll ans=0;
void dfs(int v, ll w)
{
	M[v][w]=1;
	if(v==n) ans=max(ans,w);
	for(pair<int,ll> pr : adj[v]){
		int u=pr.first;
		ll wei=pr.second;
		if(w*wei <= P[u] && !M[u][w*wei]){
			dfs(u, w*wei);
		}
	}
}

void solve()
{
	int m;
	n = read();
	m = read();
	for(int i=1;i<=n;i++){
		P[i] = read();
		adj[i].clear();
		M[i].clear();
	}
	for(int i=0;i<m;i++){
		int a,b;
		ll w;
		a = read();
		b = read();
		w = read();
		adj[a].push_back({b,w});
	}
	ans=0;
	dfs(1, 1);
	if(ans==0) cout << -1 << "\n";
	else cout << ans << "\n";
}

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