Farmer John odkrył sekret najsłodszego masła w Wisconsin: cukier. Kostkę na pastwisku poliże $N$ krów ($1\le N\le500$), dając bardzo słodkie masło sprzedawane drożej. Dodatkowe pieniądze oczywiście wydaje na luksusy dla krów.

FJ jest sprytny. Jak dawniej Pavlov, wie, jak nauczyć krowy chodzić na konkretne pastwisko na dźwięk dzwonka. Umieści tam cukier i zadzwoni w środku popołudnia, by wieczorny udój dał idealne mleko.

Każda krowa spędza czas na danym pastwisku, niekoniecznie sama. Z miejsc i ścieżek znajdź pastwisko cukru minimalizujące sumę odległości po dzwonku. Połączeń wystarcza, by zawsze było rozwiązanie.

Wejście

• Wiersz $1$: całkowite ze spacjami, liczba krów $N$, pastwisk $P$ ($2\le P\le800$), ścieżek $C$ ($1\le C\le1{,}450$). Unikalne numery $1\ldots N$ dla krów, $1\ldots P$ dla pastwisk.

• Wiersze $2\ldots N+1$: całkowity numer pastwiska krowy; krowa $i$ w wierszu $i+1$.

• Wiersze $N+2\ldots N+C+1$: trzy całkowite ze spacjami, dwa pastwiska i długość. Ścieżki dwukierunkowe, najwyżej jedna bezpośrednia na parę. Pierwsze dwie liczby w $1\ldots P$, trzecia w $1\ldots225$.

Wyjście

• Wiersz $1$: całkowita minimalna suma odległości krów do pastwiska z cukrem.

Przykład

Wejście 1

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

Wyjście 1

8

Uwagi

Diagram pokazuje połączenia geometrycznie:

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

Cukier w $4$ oznacza, że krowa $1$ idzie $3$ jednostki, $2$ idzie $5$, $3$ idzie $0$, razem $8$.

Autor zadania: Greg Galperin, 2001