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

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> p(n);
  for(int i = 0; i < n; i++) cin >> p[i];
  vector<vector<pair<int, ll>>> g(n);
  for(int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  vector<unordered_set<int>> u(n);
  queue<pair<int, ll>> q;
  q.push({0, 1});
  u[0].insert(1);
  while(!q.empty()) {
    auto [v, d] = q.front();
    q.pop();
    for(auto [to, c] : g[v]) {
      ll nd = c * d;
      if(nd <= p[to] && !u[to].contains(nd)) {
        q.push({to, nd});
        u[to].insert(nd);
      }
    }
  }
  int ans = -1;
  for(int x : u[n - 1]) ans = max(ans, x);
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

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