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

#define all(a) begin(a), end(a)
using ll = long long;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        // static const auto FIXED_RANDOM = random_device{}();
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

vector<int> get_fracs(int n) {
    vector<int> a;
    for (int i = 1; i <= n; i++) {
        int t = n / i;
        a.push_back(t);
        i = n / t;
    }

    return a;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector<ll> a(n);
    for (auto &i : a)
        cin >> i;

    vector<vector<pair<int, ll>>> G(n), rev(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;

        G[u].push_back({v, w});
        rev[v].push_back({u, w});
    }

    vector<int> vals;
    for (auto i : a) {
        auto t = get_fracs(i);
        vals.insert(end(vals), all(t));
    }

    sort(all(vals));
    vals.erase(unique(all(vals)), end(vals));
    const int k = vals.size();

    unordered_map<int, int, custom_hash> to_pos;
    for (int i = 0; i < k; i++)
        to_pos[vals[i]] = i;

    vector<vector<pair<ll, int>>> layers(k);

    auto push = [&](int vertex, ll limit, ll suffix) {
        limit = min(limit, a[vertex]);
        if (limit == 0)
            return;

        // Maybe use hash map ?
        // auto it = lower_bound(all(vals), limit);
        // assert(it < end(vals) && *it == limit);
        // int ind = it - begin(vals);

        int ind = to_pos.at(limit);
        layers[ind].push_back({suffix, vertex});
    };

    push(n - 1, a[n - 1], 1);

    vector<int> last(n, -1);
    for (int h = k - 1; h >= 0; --h) {
        auto &l = layers[h];
        const int limit = vals[h];

        sort(all(l));
        while (!l.empty()) {
            auto [suffix, u] = l.back();
            l.pop_back();

            if (suffix <= last[u])
                continue;
            last[u] = suffix;

            for (auto [v, w] : rev[u])
                push(v, limit / w, suffix * w);
        }
    }

    cout << last[0] << "\n";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int tests = 1;
    cin >> tests;

    while (tests--)
        solve();
}