Przemytnicy

Limit pamięci: 32 MB

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 w metal 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:

• Wczyta tabelę cen wszystkich metali, a także ceny przemian oferowanych przez alchemików.
• Wyznaczy taki ciąg metali , że:
  • to złoto,
  • dla każdego alchemicy potrafią otrzymać metal z metalu , oraz
  • koszt wykonania całego ciągu procesów alchemicznych dla 1 kg złota, powiększony o płacone na granicy cło (50% ceny 1 kg najtańszego z metali , dla ) jest najmniejszy z możliwych.
  Zakładamy, że podczas procesów alchemicznych waga metali nie zmienia się.
• Wypisze koszt wykonania wyznaczonego ciągu procesów alchemicznych powiększony o płacone na granicy cło.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita oznaczająca liczbę rodzajów metali, . W wierszu o numerze , dla , znajduje się nieujemna parzysta liczba całkowita - cena 1 kg metalu oznaczonego numerem , . Przyjmujemy, że złoto ma numer 1. W wierszu o numerze znajduje się jedna nieujemna liczba całkowita równa liczbie procesów przemiany znanych alchemikom, . W każdym z kolejnych wierszy znajdują się po trzy liczby naturalne, pooddzielane pojedynczymi odstępami, opisujące kolejne procesy przemiany. Trójka liczb oznacza, że alchemicy potrafią z metalu o numerze otrzymywać metal o numerze i za zamianę 1 kg surowca każą sobie płacić bajtalarów, . Uporządkowana para liczb i 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

poprawną odpowiedzią jest:

60

Autor zadania: Łukasz Kowalik.