#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef LOCAL
#include "../debug/debug.h"
#else
#define debug(...)
#define debugArr(...)
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = long double;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;

#define mp make_pair
#define eb emplace_back
#define pb push_back
#define x first
#define y second
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend() 
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define ft front()
#define bk back()
#define rsz resize
#define ins insert
#define each(a,x) for(auto&a:x)

template<class T> bool ckmin(T& a, T b) { return b<a?a=b,1:0; }
template<class T> bool ckmax(T& a, T b) { return b>a?a=b,1:0; }
template<class T> int lwb(vector<T>& a, const T& b) { return int(lower_bound(all(a),b)-bg(a)); }
template<class T> int upb(vector<T>& a, const T& b) { return int(upper_bound(all(a),b)-bg(a)); }
template<class T> void remdup(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }

constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bitlog(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
constexpr int pct(ll x) { return __builtin_popcountll(x); }
constexpr int bitlog(ll x) { return x == 0 ? 0 : 63 - __builtin_clzll(x); }

constexpr ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }  // divide a by b rounded up
constexpr ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }  // divide a by b rounded down
constexpr int cdiv(int a, int b) { return a / b + ((a ^ b) > 0 && a % b); }  // divide a by b rounded down
constexpr int fdiv(int a, int b) { return a / b - ((a ^ b) < 0 && a % b); }  // divide a by b rounded down

const pi MOVES[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

#ifdef LOCAL
mt19937_64 rng(0xabadbeef);
#else
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

ll randr(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }

const int INF = 1e9 + 10;
struct SegmentSet {
    set<pi> s;
    
    bool add(int x, int y) {
        auto it = s.upper_bound(mp(x, INF));

        if (it != bg(s) && prev(it)->x <= x && prev(it)->y >= y) {
            return false;
        }

        while (it != end(s) && it->x <= y + 1) {
            ckmin(x, it->x);
            ckmax(y, it->y);
            it = s.erase(it);
        }

        // it jest "za" moim przedziałem
        while (it != bg(s) && (--it)->y + 1 >= x) {
            ckmin(x, it->x);
            ckmax(y, it->y);
            it = s.erase(it);
        }

        s.emplace(x, y);
        return true;
    }

    void clear() {
        s.clear();
    }
};

const int N = 108;
const int M = 208;
int p[N];
vpi g[N];
vpi gr[N];
vi g1[N];
int reachable[N][N]; // with 1-edges
vi reachable_vector[N];
SegmentSet memo[N];
int n, m;

bool achievable_simple(int u, int lx, int rx);
bool achievable_complex(int u, int lx, int rx);

bool achievable_simple(int u, int lx, int rx) {
    if (lx == 1 && reachable[0][u] != -1) {
        return true;
    }

    if (!memo[u].add(lx, rx)) {
        return false;
    }

    for (auto [v, w] : gr[u]) {
        int new_lx = (lx + w - 1) / w;
        if (new_lx > p[v]) continue;
        int new_rx = min(p[v], rx / w);
        if (new_rx < new_lx) continue;

        if (achievable_complex(v, new_lx, new_rx)) {
            return true;
        }
    }

    return false;
}

bool achievable_complex(int u, int lx, int rx) {
    if (lx == 1 && reachable[0][u] != -1) {
        return true;
    }

    if (!memo[u].add(lx, rx)) {
        return false;
    }

    for (auto [v, w] : gr[u]) {
        int new_lx = (lx + w - 1) / w;
        if (new_lx > p[v]) continue;
        int new_rx = min(p[v], rx / w);
        if (new_rx < new_lx) continue;
        if (achievable_complex(v, new_lx, new_rx)) {
            return true;
        }
    }

    for (auto v : reachable_vector[u]) {
        if (lx > reachable[v][u]) break;
        int new_rx = min(rx, reachable[v][u]);
        if (achievable_simple(v, lx, new_rx)) {
            return true;
        }
    }

    return false;
}

bool calc(int x) {
    return achievable_complex(n - 1, x, p[n - 1]);
}

void init_reachable() {
    rep(i,0,n) rep(j,0,n) reachable[i][j] = -1;

    rep(i,0,n) {
        priority_queue<pi> pq;
        pq.emplace(p[i], i);
        reachable[i][i] = p[i];
        while (!pq.empty()) {
            auto [x, j] = pq.top();
            pq.pop();
            assert(reachable[i][j] == x);
            for (auto k : g1[j]) {
                int nx = min(x, p[k]);
                if (ckmax(reachable[i][k], nx)) {
                    pq.emplace(nx, k);
                }
            }
        }
    }

    rep(i,0,n) {
        rep(j,0,n) {
            if (reachable[j][i] != -1 && i != j) {
                reachable_vector[i].eb(j);
            }
        }
        sort(all(reachable_vector[i]), [&](int u, int v) {
            return reachable[u][i] > reachable[v][i];
        });
    }
}

void solve() {
    cin >> n >> m;
    rep(i,0,n) cin >> p[i];
    rep(i,0,n) memo[i].clear();
    rep(i,0,n) {
        g[i].clear();
        gr[i].clear();
        g1[i].clear();
        reachable_vector[i].clear();
    }
    rep(i,0,m) {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        if (w == 1) {
            g1[a].eb(b);
        }
        else {
            g[a].eb(b, w);
            gr[b].eb(a, w);
        }
    }
    init_reachable();

    int res = -1;
    int l = 1;
    int r = p[n - 1];

    while (l <= r) {
        int mid = (l + r) / 2;
        if (calc(mid)) {
            l = mid + 1;
            res = mid;
            rep(i,0,n) memo[i].clear();
        }
        else {
            r = mid - 1;
        }
    }

    cout << res << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;
    rep(tc,0,t) {
        if (tc % 10 == 0) {
            debug(tc);
        }
        solve();
    }

    return 0;
}