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
#include <stdio.h>
#include <set>
#include <queue>
#include <unordered_set>

using namespace std;

#define N 100
#define M 200
#define lli long long int

int t,ti,n,m,riz,rido;
lli riwart;

struct router {
    lli przep;
    unordered_set<lli> zrobione;
    std::set<pair<int, lli> > wzmacniacze;
};
router r[N];

queue<pair<int, lli> > kolejka;

int main() {
    scanf("%d",&t);
    for (ti=0;ti<t;ti++) {
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++) {
            scanf("%lld",&r[i].przep);
            r[i].zrobione = unordered_set<lli>();
            r[i].wzmacniacze = std::set<pair<int, lli> >();
        }
        for (int i=0;i<m;i++) {
            scanf("%d%d%lld",&riz,&rido,&riwart);
            r[riz-1].wzmacniacze.insert(make_pair(rido-1,riwart));
            //scanf("%d%d%lld",&wzm[i].z,&wzm[i].do,&wzm[i].wsp);
        }
        kolejka.push(make_pair(0,1));
        
        while(!kolejka.empty()) {
            auto akt = kolejka.front();
            kolejka.pop();
            //printf("Robimy %d %lld\n",akt.first,akt.second);
            if(r[akt.first].zrobione.find(akt.second) != r[akt.first].zrobione.end()) {
                continue;
            } else {
                for(auto [do_,wsp] : r[akt.first].wzmacniacze) {
                    if(r[do_].przep >= akt.second*wsp) {
                        kolejka.push(make_pair(do_,akt.second*wsp));
                    }
                }
                r[akt.first].zrobione.insert(akt.second);
            }
        }

        /*if(r[n-1].zrobione.size()==0) {
            printf("-1\n");
        } else {
            auto it = r[n-1].zrobione.rbegin();
            printf("%lld\n", *it);
        }*/
       lli res = -1;
       for(auto x : r[n-1].zrobione) {
           if(x > res) {
               res = x;
           }
       }
       printf("%lld\n",res);
    }
    return 0;
}