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
def solve_heavy_metal():
    T = int(input())
    results = []
    
    for _ in range(T):
        n, m = map(int, input().split())
        capacities = list(map(int, input().split()))
        
        # Budujemy graf połączeń między ruterami
        graph = [[] for _ in range(n+1)]
        for i in range(m):
            a, b, w = map(int, input().split())
            graph[a].append((b, w))
        
        # Używamy zmodyfikowanego algorytmu do znajdowania maksymalnych wzmocnień
        max_gain = find_max_gain(n, capacities, graph)
        results.append(max_gain)
    
    return results

def find_max_gain(n, capacities, graph):
    # Używamy dynamicznego programowania do śledzenia maksymalnego wzmocnienia
    # dla każdego rutera i każdej możliwej mocy sygnału
    
    import collections
    
    # Zaczynamy z rutera 1 z mocą sygnału 1
    start_router = 1
    start_power = 1
    
    # Kolejka do BFS z (ruter, moc_sygnału)
    queue = collections.deque([(start_router, start_power)])
    
    # Dla każdego rutera trzymamy najlepsze osiągnięte wzmocnienie
    best_gain = {start_router: start_power}
    
    # Zbiór odwiedzonych stanów (ruter, moc_sygnału) aby unikać cykli
    visited = set()
    
    # Zmienna do śledzenia najlepszego wzmocnienia dla rutera docelowego
    best_for_target = 0
    
    # Ograniczenie na liczbę iteracji aby uniknąć zapętlenia
    iteration_limit = 10000
    iterations = 0
    
    while queue and iterations < iteration_limit:
        iterations += 1
        current_router, current_power = queue.popleft()
        
        # Jeśli dotarliśmy do rutera docelowego, aktualizujemy najlepsze wzmocnienie
        if current_router == n and current_power > best_for_target:
            best_for_target = current_power
        
        # Stan odwiedzony, pomijamy
        if (current_router, current_power) in visited:
            continue
        
        visited.add((current_router, current_power))
        
        # Sprawdzamy wszystkie wzmacniacze wychodzące z obecnego rutera
        for next_router, amplifier_gain in graph[current_router]:
            # Obliczamy nową moc sygnału po wzmacniaczu
            new_power = current_power * amplifier_gain
            
            # Sprawdzamy, czy moc nie przekracza przepustowości następnego rutera
            if new_power <= capacities[next_router-1]:
                # Jeśli to nowe najlepsze wzmocnienie dla tego rutera, aktualizujemy
                best_gain[next_router] = max(best_gain.get(next_router, 0), new_power)
                
                # Dodajemy nowy stan do kolejki
                queue.append((next_router, new_power))
    
    # Jeśli nie udało się dotrzeć do rutera docelowego, zwracamy -1
    return best_for_target if best_for_target > 0 else -1

def main():
    results = solve_heavy_metal()
    for result in results:
        print(result)

if __name__ == "__main__":
    main()