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
from sys import stdin, stdout
from collections import defaultdict

T = int(stdin.readline())

for _ in range(T):
    no_routers, no_amplifier = [int(x) for x in stdin.readline().split()]
    router_bandwidth = [-1] +[int(x) for x in stdin.readline().split()]
    amp_desc = []
    for _ in range(no_amplifier):
        amp_desc.append([int(x) for x in stdin.readline().split()])
    # print(f"{amp_desc=}")

    router_out = defaultdict(list)
    for amp in amp_desc:
        router_out[amp[0]].append(amp)

    possible_states = [(1, 1)]
    seen_possible_states = {(1, 1)}
    i = 0
    while i < len(possible_states):
        router, power = possible_states[i]
        for amp in router_out[router]:
            out = amp[1]
            new_power = power * amp[2]
            if router_bandwidth[out] >= new_power:
                if (out, new_power) not in seen_possible_states:
                    possible_states.append((out, new_power))
                    seen_possible_states.add((out, new_power))
        i += 1
        # print(f"{possible_states=}")

    speaker_outs = [-1] + [state[1] for state in possible_states if state[0] == no_routers]
    stdout.write(str(max(speaker_outs)) + "\n")