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 <bits/stdc++.h>
#define pie pair<int, int>
using namespace std;

struct node {
    int capacity;
    set<pie> neigh;           //index, multiplier
    set<pie> rev;         //revGraph, also index, multiplier
    set<int> usedMults;
    int prevValue;          //previously checked value (should be removed from usedMults)
};

bool prepare(int n, vector<node> &graph) {
    //shrink capacity to reasonable values, remove leaves TODO: and cycles of multiplier 1
    vector<int> capacity(n+1);
    for(int i=0; i<=n; i++) {           //maximal capacity
        capacity[i] = graph[i].capacity;
        graph[i].capacity = 0;
    }
    graph[n].capacity = capacity[n];
    priority_queue<pie, vector<pie>, less<>> pq;            //max at the top
    pq.emplace(n, graph[n].capacity);
    while(!pq.empty()) {
        pie cur = pq.top();
        pq.pop();
        if(cur.second < graph[cur.first].capacity)
            continue;           //not the best anyway
        for(const pie &next : graph[cur.first].rev) {         //for all predecessors
            int cap = cur.second/next.second;
            if(cap > graph[next.first].capacity) {          //better
                graph[next.first].capacity = min(cap, capacity[next.first]);
                pq.emplace(next.first, graph[next.first].capacity);
            }
        }
    }

    //remove leaves
    if(graph[1].capacity == 0)          //can't get to the end
        return false;
    for(int i=2; i<=n; i++) {
        if(graph[i].capacity == 0) {            //no possible way to get to the end -> delete that vertex
            for(const pie &cur : graph[i].neigh) {
                graph[cur.first].rev.erase({i, cur.second});
            }
            for(const pie &cur : graph[i].rev) {
                graph[cur.first].neigh.erase({i, cur.second});
            }
        }
    }

    //remove cycles with multiplier 1
    //TODO: optional


    return true;
}

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

    int z;
    cin >> z;
    while(z--) {
        int n, m;           //vertices and edges
        cin >> n >> m;
        vector<node> graph(n+1);            //input is 1-indexed
        for(int i=1; i<=n; i++)
            cin >> graph[i].capacity;
        for(int i=0; i<m; i++) {
            int from, to, multiplier;
            cin >> from >> to >> multiplier;
            graph[from].neigh.emplace(to, multiplier);
            graph[to].rev.emplace(from, multiplier);
        }

        if(!prepare(n, graph)) {            //failed to prepare
            cout << "-1\n";
            continue;
        }

        //search for that path
        priority_queue<pie, vector<pie>, greater<>> pq;         //value, index
        pq.emplace(1, 1);
        graph[1].usedMults.emplace(1);
        while(!pq.empty()) {
            pie cur = pq.top();         //value, index
            pq.pop();
            for(const pie &next : graph[cur.second].neigh) {            //index, multiplier
                long long int newValue = (long long int)cur.first * next.second;
                if(newValue > graph[next.first].capacity)
                    continue;           //too much power
                else if(graph[next.first].usedMults.count(newValue))
                    continue;           //already has that value
                //else -> add to pq and graph[cur.second].usedMults
                pq.emplace(newValue, next.first);
                graph[next.first].usedMults.emplace(newValue);
            }
            graph[cur.second].usedMults.erase(graph[cur.second].prevValue);
            graph[cur.second].prevValue = cur.first;
        }

        cout << graph[n].prevValue << "\n";
    }
    return 0;
}