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

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2")

#define int long long

using namespace std;

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		int n, m;
		cin >> n >> m;
		vector<int> limits(n);
		for (int i = 0; i < n; i++)
		{
			int p;
			cin >> p;
			limits[i] = p;
		}
		vector<vector<pair<int, int>>> graph(n);
		for (int i = 0; i < m; i++)
		{
			int a, b, w;
			cin >> a >> b >> w;
			a--;
			b--;
			graph[a].push_back({b, w});
		}

		vector<set<int>> possible(n);

		int wynik = -1;

		possible[0].insert(1);
		while (true)
		{
			bool changed = false;
			for (int i = 0; i < n; i++)
			{
				// propagate from i to neighbours
				for (auto curr_poss : possible[i])
				{
					for (int j = 0; j < graph[i].size(); j++)
					{
						auto edge = graph[i][j];
						int neigh = edge.first;

						int new_val = curr_poss * edge.second;
						// cerr << "from " << i << " to " << neigh << " * " << edge.second << " gives " <<
						if (new_val <= limits[neigh])
						{
							int old_size = possible[neigh].size();
							possible[neigh].insert(new_val);
							int new_size = possible[neigh].size();
							if (neigh == n - 1)
							{
								wynik = max(wynik, new_val);
							}
							if (old_size != new_size)
								changed = true;
						}
					}
				}
			}
			if (!changed)
				break;
		}
		cout << wynik << endl;
	}
}