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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
const ll INF = 1e9 + 7;

ll ans;
int n, m;
int used[105];
int idx_self[105];
set <array<ll, 2>> st[105];

void dfs(vector <vector <pair <ll, ll>>> &g, vector <vector <ll>> &loops, vector <ll> &p, vector <bool> &flag, vector <ll> &dist, vector <ll> &neck, ll v, ll cur) {
    if (st[v].count({cur, idx_self[v]})) return;
    else st[v].insert({cur, idx_self[v]});
    if (v == n) {
        ans = max(ans, cur);
    }
    if (neck[v] < cur || cur * dist[v] > p[n]) return;
    
    if (!used[v]) {
        if (idx_self[v] < loops[v].size() && cur * loops[v][idx_self[v]] <= p[v]) 
            dfs(g, loops, p, flag, dist, neck, v, cur * loops[v][idx_self[v]]);
        if (idx_self[v] + 1 < loops[v].size()) {
            idx_self[v]++;
            dfs(g, loops, p, flag, dist, neck, v, cur);
            idx_self[v]--;
        }
    }

    used[v]++;
    for (int i = 0; i < g[v].size(); i++) {
        auto [e, w] = g[v][i];
        if (!flag[e]) continue;
        if (cur * w <= p[e]) {
            dfs(g, loops, p, flag, dist, neck, e, cur * w);
        }
    }
    used[v]--;
}

void solve() {
    cin >> n >> m;
    vector <ll> p(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> p[i];
    vector <vector <pair <ll, ll>>> g(n + 1), gr(n + 1);
    set <array<ll, 3>> edges;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        if (!(a == b && w == 1)) edges.insert({a, b, w});
        g[a].push_back({b, w});
        gr[b].push_back({a, w});
    }

    vector <bool> flag(n + 1, false);
    queue <int> q;
    flag[n] = true;
    q.push(n);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto [e, w] : gr[cur]) {
            if (!flag[e]) {
                flag[e] = true;
                q.push(e);
            }
        }
    }

    if (!flag[1]) {
        cout << -1 << '\n';
        return;
    }

    vector <ll> dist(n + 1, INF);
    priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater<pair <ll, int>>> pq;
    dist[1] = 1;
    pq.push({1, 1});
    while (!pq.empty()) {
        ll t = pq.top().first, cur = pq.top().second;
        pq.pop();
        if (t != dist[cur]) continue; 
        for (auto [e, w] : g[cur]) { if (flag[e])
            if (t * w < dist[e] && t * w <= p[e]) {
                dist[e] = t * w;
                pq.push({t * w, e});
            }
        }
    }

    if (dist[n] == INF) {
        cout << -1 << '\n';
        return;
    }
    ans = dist[n];

    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[n] = 1;
    pq.push({1, n});
    while (!pq.empty()) {
        ll t = pq.top().first, cur = pq.top().second;
        pq.pop();
        if (t != dist[cur]) continue;
        for (auto [e, w] : gr[cur]) if (flag[e]) {
            if (t * w < dist[e]) {
                dist[e] = t * w;
                pq.push({t * w, e});
            }
        }
    }

    vector <ll> neck(n + 1, 0);
    neck[n] = INF;
    priority_queue <pair <ll, int>> pq2;
    pq2.push({INF, n});
    while (!pq2.empty()) {
        ll val = pq2.top().first, cur = pq2.top().second;
        pq2.pop();
        if (val != neck[cur]) continue;
        for (auto [e, w] : gr[cur]) if (flag[e]) {
            if (min(val, p[e]) > neck[e]) {
                neck[e] = min(val, p[e]);
                pq2.push({neck[e], e});
            }
        }
    }

    vector <vector <ll>> loops(n + 1);
    for (int i = 1; i <= n; i++) g[i].clear();
    for (auto [a, b, w] : edges) {
        if (a == b) loops[a].push_back(w);
        else g[a].push_back({b, w});
    }

    for (int i = 1; i <= n; i++) {
        used[i] = 0;
        idx_self[i] = 0;
        st[i].clear();
    }

    dfs(g, loops, p, flag, dist, neck, 1, 1);
    cout << ans << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}