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

const int MAXN = 107;

void solve_case() {
	int n, m; cin >> n >> m;
	vector<int> p(n + 1);
	for (int i = 1; i <= n; ++i) cin >> p[i];
	vector<pair<pair<int, int>, int> > edges;
	for (int i = 0; i < m; ++i) {
		int a, b, c; cin >> a >> b >> c;
		edges.push_back({{a, b}, c});
	}
	unordered_map<int, bool> dist[MAXN];
	dist[1][1] = 1;
	const int ITERS = n * n + 20;
	bool stop = 0;
	for (int i = 0; i < ITERS; ++i) {
		int opers = 0;
		for (auto &e : edges) {
			int u = e.first.first, v = e.first.second, w = e.second;
			if (u == v && w == 1) continue;
			opers += dist[u].size();
			if (opers > 2e6) {
				stop = 1;
				break;
			}
			if (u == v) {
				unordered_map<int, bool> tmp = dist[u];
				for (auto pi : tmp) {
					if ((long long)pi.first * w <= p[v]) dist[v][pi.first * w] = 1;
				}
			}
			else {
				for (auto pi : dist[u]) {
					if ((long long)pi.first * w <= p[v]) dist[v][pi.first * w] = 1;
				}
			}
		}
		if (stop) break;
	}
	int best = -1;
	for (auto pi : dist[n]) {
		best = max(best, pi.first);
	}
	cout << best << "\n";
}

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