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
//fast
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define rep(n) for (int i = 0 ; i<n ; i++)
#define pb push_back

const int base = 103;
const int maxd = 100;
vector<pair<int,ll>> graf[base];
ll p[base];
int n;

ll w = -1;

void dfs(int v, int d, ll x){
	if (x>p[v]) return;
	if (v==n) w = max(w,x);
	if (d>maxd) return;
	for (auto i : graf[v]){
		dfs(i.first,d+1,x*i.second);
	}
}

void solve(int ttt){
	w = -1;
	int m;
	cin >> n >> m;
	rep(n) cin >> p[i+1];
	rep(n+2) graf[i] = {};
	rep(m){
		int a,b,w;
		cin >> a >> b >> w;
		graf[a].pb({b,w});
	}
	dfs(1,0,1);
	cout << w << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    rep(t) solve(i);
}