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
#include <iostream>
#include <set>
#include <vector>
#include <queue>

const int MAX = 102;

int W[MAX];
struct edge{
    int b;
    int w;
};
struct DD{
    int b;
    int w;
    int o;
};
std::vector<edge> E[MAX];
std::vector<edge> E2[MAX];
std::set<int> D[MAX];
std::set<std::pair<int, int>> D2[MAX];

int BFS(int n) {
    std::queue<edge> Q1[2];
    std::queue<DD> Q2[2];

    Q1[0].push({1,1});
    Q2[0].push({n,1,W[n]});

    int best = -1;

    while (!Q1[0].empty()) {
        while (!Q1[0].empty()) {
            auto[a, w] = Q1[0].front();
            // std::clog << a << " w " << w << std::endl;
            Q1[0].pop();
            for (const auto[b, ww] : E[a]) {
                if (W[b] < int64_t(ww)*w) continue; // przepalone
                if (int www = ww*w; D[b].count(www) == 0) {
                    D[b].insert(www);
                    Q1[1].push({b, www});
                }
            }
        }
        std::swap(Q1[0], Q1[1]);

        while (!Q2[0].empty()) {
            auto[a, w, o] = Q2[0].front();
            Q2[0].pop();

            auto it = D[a].lower_bound(o);
            if (it == D[a].end()) it = D[a].rbegin().base();
            if (it != D[a].end() && *it <= o) {
                // std::clog << " A :: " << best << " " << *it << " " << w << " " << o<< std::endl;
                best = std::max(best, *it*w);
            }

            for (const auto[b, ww] : E2[a]) {
                int oo = std::min(W[b], o/ww);
                if (oo < 1) continue; // przepalone

                auto it = D[b].lower_bound(oo);
                if (it == D[b].end()) it = D[b].rbegin().base();
                if (it != D[b].end() && *it <= oo) {
                    // std::clog << " B :: " << best << " " << *it << " " << ww*w << " " << oo << std::endl;
                    best = std::max(best, *it*ww*w);
                }

                if (int www = ww*w; D2[b].count({www, oo}) == 0) {
                    D2[b].insert({www, oo});
                    Q2[1].push({b, www, oo});
                }
            }
        }
        std::swap(Q2[0], Q2[1]);
    }
    return best;
}

void solve() {
    int n,m;
    std::cin >> n >> m;
    for (int i=1;i<=n;++i) {
        E[i].clear();
        E2[i].clear();
        D[i].clear();
        D2[i].clear();
    }
    for (int i=1;i<=n;++i) std::cin >> W[i];
    for (int i=0;i<m;++i) {
        int a,b,w;
        std::cin >> a >> b >> w;
        E[a].push_back({b,w});
        E2[b].push_back({a,w});
    }
    std::cout << BFS(n) << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(0);

    int t;
    std::cin >> t;
    while (t--) solve();

    return 0;
}