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
import heapq

def solve():
    T = int(input())  # Liczba zestawów nagłaśniających
    for _ in range(T):
        n, m = map(int, input().split())  # Liczba ruterów i wzmacniaczy
        p = list(map(int, input().split()))  # Przepustowości ruterów
        adj = [[] for _ in range(n)]  # Macierz sąsiedztwa (graf)

        # Wczytanie wzmacniaczy
        for _ in range(m):
            a, b, w = map(int, input().split())
            a -= 1  # Przesuwamy indeksy do 0
            b -= 1
            adj[a].append((b, w))
            adj[b].append((a, w))  # Wzmacniacze są dwukierunkowe

        # Algorytm dijkstra do znajdowania maksymalnej mocy sygnału
        max_power = [0] * n  # Przechowuje maksymalną moc sygnału dla każdego rutera
        max_power[0] = 1  # Moc sygnału z mikrofonu (początkowo 1 na ruterze 1)
        
        # Stos używany do implementacji Dijkstry (używamy max-heap, dlatego musimy negować wartości)
        heap = [(-1, 0)]  # (moc, indeks rutera)
        
        while heap:
            power, node = heapq.heappop(heap)
            power = -power  # Przekształcamy z powrotem do pozytywnej mocy
            if power < max_power[node]:
                continue

            for neighbor, gain in adj[node]:
                new_power = power * gain
                if new_power <= p[neighbor] and new_power > max_power[neighbor]:
                    max_power[neighbor] = new_power
                    heapq.heappush(heap, (-new_power, neighbor))
        
        # Wynik dla tego zestawu nagłaśniającego
        if max_power[n-1] == 0:
            print(-1)
        else:
            print(max_power[n-1])

# Wywołanie funkcji głównej
if __name__ == "__main__":
    solve()