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
#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

const int N = 101;
const int S = 32000;
using A = array<int, 3>;
int n, m;
int p[N];
vector<pii> g[N], r[N];
bool vis[N][S];
int dp[N][S];

void dfs(int u, int x) {
  vis[u][x] = 1;
  for (auto [v, w] : g[u]) {
    ll y = 1ll * x * w;
    if (y < S && y <= p[v] && !vis[v][y]) {
      dfs(v, y);
    }
  }
}

bool cmp(const A& a, const A& b) {
  if (a[0] != b[0]) return a[0] < b[0];
  return 0;
}

void solve() {
  cin >> n >> m;
  rep(i, 0, n) {
    g[i].clear();
    r[i].clear();
    rep(j, 0, S) {
      vis[i][j] = 0;
      dp[i][j] = -1;
    }
  }
  rep(i, 0, n) cin >> p[i];
  rep(i, 0, m) {
    int u, v, w;
    cin >> u >> v >> w;
    u--; v--;
    g[u].push_back({v, w});
    r[v].push_back({u, w});
  }
  dfs(0, 1);
  priority_queue<A, vector<A>, decltype(&cmp)> q(cmp);
  dp[n - 1][1] = p[n - 1];
  q.push({p[n - 1], n - 1, 1});
  while (sz(q)) {
    auto [d, u, x] = q.top(); q.pop();
    if (d != dp[u][x]) continue;
    for (auto [v, w] : r[u]) {
      ll y = 1ll * x * w;
      int d2 = min(p[v], d / w);
      if (y < S && d2 > dp[v][y]) {
        dp[v][y] = d2;
        q.push({dp[v][y], v, y});
      }
    }
  }
  int odp = -1;
  rep(i, 0, n) for (int j = S - 2; j >= 0; j--) dp[i][j] = max(dp[i][j], dp[i][j + 1]);
  rep(i, 0, n) for (auto [j, w] : g[i]) {
    int l = S - 1;
    rep(k, 0, S) if (vis[i][k]) {
      while (l > 0 && dp[j][l] < 1ll * k * w) l--;
      if (dp[j][l] >= 1ll * k * w) odp = max(odp, k * w * l);
    }
  }
  rep(i, 0, S) if (vis[n - 1][i]) odp = max(odp, i);
  cout << odp << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
}