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
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#define DEBUG false

using namespace std;


struct edge {
    int target;
    long long value;

    bool operator< (const edge &other) {
        if (target == other.target) {
            return value < other.value;
        }
        return target < other.target;
    }
};

struct step {
    int target;
    long long value;
};

int main() {
    int t;
    scanf("%d", &t);
    for (int t_i = 0; t_i < t; ++t_i) {
        int n, m;
        scanf("%d %d", &n, &m);
        vector<long long> maxpowers;
        vector<set<long long>> achievables;
        vector<vector<edge>> pregraph;
        vector<vector<edge>> graph;
        queue<step> next_steps;
        for (int i = 0; i < n; ++i) {
            long long p;
            scanf("%lld", &p);
            maxpowers.push_back(p);
            achievables.emplace_back();
            pregraph.emplace_back();
            graph.emplace_back();
        }
        for (int i = 0; i < m; ++i) {
            int a, b;
            long long w;
            scanf("%d %d %lld", &a, &b, &w);
            pregraph[a-1].push_back({b-1, w});
        }
        if constexpr(DEBUG) printf("Done reading the input!\n");
        for (int i = 0; i < n; ++i) {
            if constexpr(DEBUG) printf("Cleaning up graph %2d\n", i);
            sort(pregraph[i].begin(), pregraph[i].end());
            if constexpr(DEBUG) printf("    sorted...\n");
            int prev_target_id = -1;
            long long prev_value = -1;
            for (int j = 0; j < pregraph[i].size(); ++j) {
                if constexpr(DEBUG) printf("  got edge %2d %6lld\n", pregraph[i][j].target, pregraph[i][j].value);
                if (pregraph[i][j].target != prev_target_id) {
                    prev_target_id = pregraph[i][j].target;
                    prev_value = -1;
                }
                if (pregraph[i][j].value != prev_value){
                    if constexpr(DEBUG) printf("      valid, pushing it\n");
                    prev_value = pregraph[i][j].value;
                    graph[i].push_back(pregraph[i][j]);
                }
            }
        }

        next_steps.push(step{0, 1});
        achievables[0].insert(1);

        while(!next_steps.empty()) {
            step top_step = next_steps.front();
            next_steps.pop();
            if constexpr(DEBUG) printf("Starting in %2d with value %9lld\n", top_step.target, top_step.value);

            for(auto edge: graph[top_step.target]) {
                long long new_strength = top_step.value * edge.value;
                if (new_strength <= maxpowers[edge.target] && !achievables[edge.target].contains(new_strength)) {
                    achievables[edge.target].insert(new_strength);
                    next_steps.push(step{edge.target, new_strength});
                    if constexpr(DEBUG) printf("Pushing vtx %2d with value %9lld\n", edge.target, new_strength);
                }
            }
        }
        if (achievables[n-1].empty()) {
            printf("-1\n");
        } else {
            auto it = achievables[n-1].end();
            it--;
            printf("%lld\n", *it);
        }
    }
    return 0;
}