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

#define ll long long

ll cap[102];
basic_string <pair<int,ll>> con[102];
unordered_set <ll> dp[102];
priority_queue <pair<ll,int>> pq;
unordered_map <int,bool> vis[102][102];

int 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;
    for(int i=1; i<=n; i++) cin >> cap[i];
    for(int i=1; i<=m; i++)
    {
      int a,b; ll w; cin >> a >> b >> w;
      if(a == b && w == 1 || vis[a][b][w]) continue;
      con[a].push_back({b,w}); vis[a][b][w]=1;
    }
    dp[1].insert(1); pq.push({1,1});
    while(!pq.empty())
    {
      auto tp = pq.top(); pq.pop();
      int v = tp.second; ll prev = tp.first;
      if(dp[v].find(prev) == dp[v].end()) continue;
      
      for(auto &e : con[v])
      {
        int u = e.first; ll act = prev*e.second;
        if(act > cap[u]) continue;
        if(dp[u].find(act) != dp[u].end()) continue;
        dp[u].insert(act); pq.push({act,u});
      }
    }
    if(!(int)dp[n].size()) cout << -1 << "\n";
    else
    {
      ll ret = 0;
      for(auto x : dp[n]) ret = max(ret,x);
      cout << ret << "\n";
    }
    for(int i=1; i<=n; i++) con[i].clear(), dp[i].clear();
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) vis[i][j].clear();
  }
}