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
// PA2025, @mjm, r5b-hea

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
using namespace std;
using lol = long long;
using ull = unsigned long long;
inline int nextInt() { int n; scanf("%d", &n); return n; }
inline ull nextUll() { ull n; scanf("%llu", &n); return n; }
inline int myMin(int a, int b) { return a <= b ? a : b; }
inline lol myMax(lol a, lol b) { return a >= b ? a : b; }

const int N = 100 + 3;
struct Edge {
	int v;
	int mn;
};

int n;
vector<Edge> g[N];
lol limit[N];

using State = pair<int, lol>;

lol solve() {
	const lol ONE = 1;
	set<State> visited;
	queue<State> q;
	q.push({ 1, ONE });
	visited.insert({ 1, ONE });
	lol res = -1;
	while (!q.empty()) {
		int a = q.front().first;
		lol p = q.front().second;
		q.pop();
		if (a == n) res = myMax(res, p);
		for (int i = 0; i < g[a].size(); ++i) {
			int b = g[a][i].v;
			int mn = g[a][i].mn;
			lol pp = p * mn;
			if (pp > limit[b]) continue;
			if (visited.count({ b, pp }) > 0) continue;
			q.push({ b, pp });
			visited.insert({ b, pp });
		}
	}
	return res;
}

int main() {
	int TC = nextInt();
	for (int tc = 0; tc < TC; ++tc) {
		n = nextInt();
		int m = nextInt();
		for (int i = 1; i <= n; ++i) {
			g[i].clear();
			limit[i] = nextInt();
		}
		for (int i = 0; i < m; ++i) {
			int a = nextInt();
			int b = nextInt();
			int w = nextInt();
			g[a].push_back({ b, w });
		}
		lol res = solve();
		printf("%lld\n", res);
	}

	return 0;
}