#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1e9 + 5;
 
int t;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
 
        vector<int> b(n + 1);
        for (int i = 1; i <= n; ++i)
            cin >> b[i];
 
        vector<vector<pair<int, int>>> adj(n + 1); // {to, weight}
        for (int i = 0; i < m; ++i) {
            int s, t, w;
            cin >> s >> t >> w;
            adj[s].emplace_back(t, w);
        }
 
        auto canReach = [&](int maxBattery) {
            vector<bool> visited(n + 1, false);
            queue<int> q;
            q.push(1);
            visited[1] = true;
 
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (auto [v, w] : adj[u]) {
                    if (w <= maxBattery && !visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            return visited[n];
        };
 
        int low = 0, high = 1e9, ans = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (canReach(mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
 
        cout << ans << '\n';
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgSU5GID0gMWU5ICsgNTsKCmludCB0OwoKaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKDApOwoKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkgewogICAgICAgIGludCBuLCBtOwogICAgICAgIGNpbiA+PiBuID4+IG07CgogICAgICAgIHZlY3RvcjxpbnQ+IGIobiArIDEpOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkKICAgICAgICAgICAgY2luID4+IGJbaV07CgogICAgICAgIHZlY3Rvcjx2ZWN0b3I8cGFpcjxpbnQsIGludD4+PiBhZGoobiArIDEpOyAvLyB7dG8sIHdlaWdodH0KICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG07ICsraSkgewogICAgICAgICAgICBpbnQgcywgdCwgdzsKICAgICAgICAgICAgY2luID4+IHMgPj4gdCA+PiB3OwogICAgICAgICAgICBhZGpbc10uZW1wbGFjZV9iYWNrKHQsIHcpOwogICAgICAgIH0KCiAgICAgICAgYXV0byBjYW5SZWFjaCA9IFsmXShpbnQgbWF4QmF0dGVyeSkgewogICAgICAgICAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZChuICsgMSwgZmFsc2UpOwogICAgICAgICAgICBxdWV1ZTxpbnQ+IHE7CiAgICAgICAgICAgIHEucHVzaCgxKTsKICAgICAgICAgICAgdmlzaXRlZFsxXSA9IHRydWU7CgogICAgICAgICAgICB3aGlsZSAoIXEuZW1wdHkoKSkgewogICAgICAgICAgICAgICAgaW50IHUgPSBxLmZyb250KCk7IHEucG9wKCk7CiAgICAgICAgICAgICAgICBmb3IgKGF1dG8gW3YsIHddIDogYWRqW3VdKSB7CiAgICAgICAgICAgICAgICAgICAgaWYgKHcgPD0gbWF4QmF0dGVyeSAmJiAhdmlzaXRlZFt2XSkgewogICAgICAgICAgICAgICAgICAgICAgICB2aXNpdGVkW3ZdID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgcS5wdXNoKHYpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gdmlzaXRlZFtuXTsKICAgICAgICB9OwoKICAgICAgICBpbnQgbG93ID0gMCwgaGlnaCA9IDFlOSwgYW5zID0gLTE7CiAgICAgICAgd2hpbGUgKGxvdyA8PSBoaWdoKSB7CiAgICAgICAgICAgIGludCBtaWQgPSAobG93ICsgaGlnaCkgLyAyOwogICAgICAgICAgICBpZiAoY2FuUmVhY2gobWlkKSkgewogICAgICAgICAgICAgICAgYW5zID0gbWlkOwogICAgICAgICAgICAgICAgaGlnaCA9IG1pZCAtIDE7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBsb3cgPSBtaWQgKyAxOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8IGFucyA8PCAnXG4nOwogICAgfQoKICAgIHJldHVybiAwOwp9Cg==

NAozIDMKMiAwIDAKMSAyIDEKMiAzIDEKMSAzIDIKNSA2CjIgMiA1IDAgMQoxIDIgMgoxIDMgMQoxIDQgMwozIDUgNQoyIDQgNAo0IDUgMwoyIDAKMSAxCjQgNAozIDEwIDAgMAoxIDIgMQoxIDMgMwoyIDMgMTAKMyA0IDUK

4
3 3
2 0 0
1 2 1
2 3 1
1 3 2
5 6
2 2 5 0 1
1 2 2
1 3 1
1 4 3
3 5 5
2 4 4
4 5 3
2 0
1 1
4 4
3 10 0 0
1 2 1
1 3 3
2 3 10
3 4 5