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 <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;
using ll = long long;

ll highest_good_amp = -1;

struct PairHash {
    size_t operator()(const pair<ll, ll>& p) const {
        return p.first ^ p.second;
    }
};

void dfs(ll n, vector<ll>& c, vector<vector<pair<ll, ll>>>& e, unordered_set<pair<ll, ll>, PairHash>& records, ll current_node, ll current_amp, ll current_depth, ll previous_node, ll previous_amp) {
    if (current_node == n - 1) {
        if (highest_good_amp < current_amp) {
            highest_good_amp = current_amp;
        }
    }

    records.insert(make_pair(current_node, current_amp));

    for (auto edge : e[current_node]) {
        ll next_node = edge.first;
        ll next_node_amp = edge.second;
        ll next_amp = current_amp * next_node_amp;

        if (next_amp > c[next_node] || records.find(make_pair(next_node, next_amp)) != records.end()) {
            continue;
        }

        dfs(n, c, e, records, next_node, next_amp, current_depth + 1, current_node, current_amp);
    }
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        ll n, m, x, y, amp;
        highest_good_amp = -1;

        cin >> n >> m;
        vector<ll> c(n);
        vector<vector<pair<ll, ll>>> e(n);
        unordered_set<pair<ll, ll>, PairHash> records;

        for (int i = 0; i < n; i++) {
            cin >> c[i];
        }

        for (int i = 0; i < m; i++) {
            cin >> x >> y >> amp;

            if (x == y && amp == 1) { // useless
                continue;
            }

            bool redundant = false;

            for (auto e : e[x - 1]) {
                if (e.first == y - 1 && e.second == amp) {
                    redundant = true;
                    break;
                }
            }

            if (!redundant) {
                e[x - 1].push_back(make_pair(y - 1, amp));;
            }
        }

        dfs(n, c, e, records, 0, 1, 0, -1, -1);
        cout << highest_good_amp << endl;
    }

    return 0;
}