html ps pdf

Przemytnicy (prz)

Bajtocja słynie z bogatych złóż złota, dlatego przez długie lata kwitła sprzedaż tego kruszcu do sąsiedniego królestwa, Bitlandii. Niestety powiększająca się ostatnio dziura budżetowa zmusiła króla Bitlandii do wprowadzenia zaporowych ceł na metale i minerały. Handlarze przekraczający granicę muszą zapłacić 50% wartości przewożonego ładunku. Bajtockim kupcom grozi bankructwo. Na szczęście bajtoccy alchemicy opracowali sposoby pozwalające zamieniać pewne metale w inne. Pomysł kupców polega na tym, aby z pomocą alchemików zamieniać złoto w pewien tani metal, a następnie, po przewiezieniu go przez granicę i zapłaceniu niewielkiego cła, znowu otrzymywać z niego złoto. Niestety alchemicy nie znaleźli sposobu na zamianę dowolnego metalu w dowolny inny. Może się więc zdarzyć, że proces otrzymania danego metalu ze złota musi przebiegać wielostopniowo i że na każdym etapie uzyskiwany będzie inny metal. Alchemicy każą sobie słono płacić za swoje usługi i dla każdego znanego sobie procesu zamiany metalu A w metal B wyznaczyli cenę za przemianę 1 kg surowca. Handlarze zastanawiają się, w jakiej postaci należy przewozić złoto przez granicę, oraz jaki ciąg procesów alchemicznych należy zastosować, aby zyski były możliwie największe.

Zadanie

Pomóż uzdrowić bajtocką gospodarkę! Napisz program, który:

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita n oznaczająca liczbę rodzajów metali, 1 <= n <= 5000. W wierszu o numerze k+1, dla 1 <= k <= n, znajduje się nieujemna parzysta liczba całkowita pk - cena 1 kg metalu oznaczonego numerem k, 0 <= pk <= 109. Przyjmujemy, że złoto ma numer 1. W wierszu o numerze n+2 znajduje się jedna nieujemna liczba całkowita m równa liczbie procesów przemiany znanych alchemikom, 0 <= m <= 100000. W każdym z kolejnych m wierszy znajdują się po trzy liczby naturalne, pooddzielane pojedynczymi odstępami, opisujące kolejne procesy przemiany. Trójka liczb a, b, c oznacza, że alchemicy potrafią z metalu o numerze a otrzymywać metal o numerze b i za zamianę 1 kg surowca każą sobie płacić c bajtalarów, 1 <= a,b <= n, 0 <= c <= 10000. Uporządkowana para liczb a i b może się pojawić w danych co najwyżej jeden raz.

Wyjście

Twój program powinien pisać na standardowe wyjście. W pierwszym wierszu powinna zostać wypisana jedna liczba całkowita - koszt wykonania wyznaczonego ciągu procesów alchemicznych powiększony o płacone na granicy cło.

Przykład

Dla danych wejściowych:

4
200
100
40
2
6
1 2 10
1 3 5
2 1 25
3 2 10
3 4 5
4 1 50

poprawnym wynikiem jest:

60

Nazwa pliku źródłowego: prz.XXX, gdzie XXX to c dla C, cpp dla C++, pas dla Pascala.