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
#include <bits/stdc++.h>
using namespace std;
const int MX=102;
int t,n,m,x,y,z,fi,fr,a[MX];
set<int> was[MX];
vector<pair<int,int>> g[MX];
pair<int,int> q[70100100];
int main() {
  scanf("%d",&t);
  while (t--) {
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) {
      scanf("%d",&a[i]);
      g[i].clear();
      was[i].clear();
    }
    for (int i=0; i<m; i++) {
      scanf("%d%d%d",&x,&y,&z);
      g[x].emplace_back(y,z);
    }
    q[0]={1,1};
    int res=-1;
    for (int fi=0,fr=1; fi<fr; fi++) {
      int x=q[fi].first;
      int cur=q[fi].second;
      if (x==n) res=max(res,cur);
      for (int j=0; j<g[x].size(); j++) {
        int nxt=g[x][j].first;
        int val=g[x][j].second;
        if (a[nxt]/val>=cur) {
          val*=cur;
          if (!was[nxt].count(val)) {
            was[nxt].insert(val);
            q[fr++]={nxt,val};
          }
        }
      }
    }
    printf("%d\n",res);
  }
  return 0;
}