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
// PA2025 runda 5B - https://sio2.mimuw.edu.pl/c/pa-2025-1/p/hea/
//-std=c++20
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<set>

using namespace std;

struct amplifier;
struct router {
    u_int64_t capacity{0};
    list<amplifier *> connected;
    bool end{false};
};
struct amplifier {
    u_int64_t strength{1};
    router *in;
    router *out;
};


int64_t traverse(amplifier *a, int64_t signal, set<amplifier *> ones);

int64_t traverse(router *r, int64_t signal, set<amplifier *> ones) {
    if (signal > r->capacity) {
        return -1;
    } else {
        vector<int64_t> signals;
        if (r->end) {
            signals.push_back(signal);
        }
        auto it = r->connected.begin();
        while (it != r->connected.end()) {
            auto x = traverse(*it, signal, ones);
            signals.push_back(x);
            it++;
        }

        if (!signals.empty()) {
            return *max_element(signals.begin(), signals.end());
        } else {
            return -1;
        }
    }
}

int64_t traverse(amplifier *a, int64_t signal, set<amplifier *> ones) {
    if (a->strength == 1 && ones.contains(a)) {
        return -1;
    } else if (a->strength == 1 && !ones.contains(a)) {
        ones.insert(a);
    }
    signal *= a->strength;
    return traverse(a->out, signal, ones);
}

void submain() {
    int n, m;
    cin >> n >> m;
    vector<router> routers;
    routers.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> routers[i].capacity;
    }
    routers[n - 1].end = true;
    vector<amplifier> amplifiers;
    amplifiers.resize(m);
    for (int i = 0; i < m; i++) {
        u_int64_t a, b, w;
        cin >> a >> b >> w;
        amplifiers[i].strength = w;
        amplifiers[i].in = &routers[a - 1];
        amplifiers[i].out = &routers[b - 1];
        routers[a - 1].connected.push_back(&amplifiers[i]);
    }
    set<amplifier *> ones;
    int64_t result = traverse(&routers[0], 1, ones);
    cout << result << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        submain();
    }
}