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
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using G = vector<vector<pair<ll, ll>>>;

struct tll
{
    ll v, power, ind;
/*    bool operator<(tll& other)
    {
        return tie(first, second, third) < 
               tie(other.first, other.second, other.third);
    }*/
};

void solve(int v, G& graph, ll value,/* vector<ll>& inds,*/ vector<unordered_set<ll>>& sets,
            vector<ll>& p);

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
    {
        ll n, m;
        cin>>n>>m;
        vector<ll> p(n);
        for(auto& x : p)
            cin>>x;
        G graph(n);
        while(m--)
        {
            ll a, b, w;
            cin>>a>>b>>w;
            graph[a-1].emplace_back(b-1, w);
        }
/*        for(int i=0; i<n; i++)
        {
            cout<<i<<": ";
            for(auto [x, y] : graph[i])
                cout<<"("<<x<<", "<<y<<") ";
            cout<<"\n";
        }*/
        vector<unordered_set<ll>> sets(n);
//        vector<ll> inds(n);
        solve(0, graph, 1,/* inds,*/ sets, p);
        sets[n-1].insert(-1);
//        cout<<"\n";
//        cout<<*sets[n-1].rbegin()<<"\n";
        cout<<*ranges::max_element(sets[n-1])<<"\n";
    }
}

void solve(int v, G& graph, ll value,/* vector<ll>& inds,*/ vector<unordered_set<ll>>& sets,
            vector<ll>& p)
{
//    cout<<"("<<v<<", "<<value<<")\n";
    if((value > p[v]) || (sets[v].contains(value)))
        return;
    sets[v].insert(value);
//    ll ind = inds[v];
    for(ll ind = 0; ind < graph[v].size(); ind++)
    {
        solve(graph[v][ind].first, graph, value * graph[v][ind].second,
            sets, p);
    }
}