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

#define ll long long
#define ve vector
#define fi first
#define se second
#define ld double
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 101;
const int MX = 1 << 15;

int mx[MAXN];
ve<pii> g[MAXN];
ve<pii> rg[MAXN];
bool dp1[MAXN][MX];
int dp2[MAXN][MX];
pii pdp[MAXN][MX];

void dfs(int v, int x)
{
    dp1[v][x] = 1;
    for (auto [to, d] : g[v])
    {
        if ((ll)x * d < MX && (ll)x * d <= mx[to] && !dp1[to][x * d])
            dfs(to, x * d);
    }
}

void bfs(int s)
{
    priority_queue<pair<int, pii>> q;
    dp2[s][1] = mx[s];
    q.push({dp2[s][1], {s, 1}});
    while (!q.empty())
    {
        auto [d, v] = q.top();
        q.pop();
        if (d != dp2[v.fi][v.se] || d == 0)
            continue;
        for (auto [to, cd] : rg[v.fi])
        {
            int cur = min(mx[to], d / cd);
            if ((ll)v.se * cd < MX && dp2[to][v.se * cd] < cur)
            {
                dp2[to][v.se * cd] = cur;
                q.push({dp2[to][v.se * cd], {to, v.se * cd}});
            }
        }
    }
}

struct edge
{
    int u, v, w;
};

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> mx[i];
        g[i].clear();
        rg[i].clear();
        //        dp2[i][0] = 1e9+7;
        memset(dp1[i], 0, sizeof(dp1[i]));
        memset(dp2[i], 0, sizeof(dp2[i]));
        fill(pdp[i], pdp[i] + MX, make_pair(0, 0));
    }
    ve<edge> es;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        rg[v].push_back({u, w});
        es.push_back({u, v, w});
    }
    es.push_back({1, 1, 1});
    dfs(1, 1);
    bfs(n);
    int res = -1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < MX; j++)
            pdp[i][j] = {dp2[i][j], j};
        sort(pdp[i], pdp[i] + MX);
        for (int j = MX - 2; j >= 0; j--)
        {
            pdp[i][j].se = max(pdp[i][j].se, pdp[i][j + 1].se);
        }
    }
    for (auto [u, v, w] : es)
    {
        for (int k = 1; k < MX; k++)
        {
            if (dp1[u][k])
            {
                pii *it = lower_bound(pdp[v], pdp[v] + MX, (ll)k * w, [](auto a, auto b)
                                      { return a.fi < b; });
                //                cout << it - pdp[v] << endl;
                if (it != pdp[v] + MX)
                {
                    res = max(res, k * w * it->se);
                }
            }
        }
    }
    cout << res << "\n";
}

signed main()
{
    int T = 1;
    cin >> T;
    while (T--){
        solve();
    }
}