Farmer John entdeckte das Geheimnis der süßesten Butter in Wisconsin: Zucker. Ein Würfel auf der Weide wird von $N$ Kühen ($1\le N\le500$) geleckt und führt zu supersüßer, teurer verkaufbarer Butter. Das zusätzliche Geld geht natürlich an Luxus für die Kühe.

FJ ist schlau. Wie einst Pavlov kann er Kühe trainieren, bei einer Glocke auf eine bestimmte Weide zu gehen. Dort legt er Zucker hin und läutet am mittleren Nachmittag für perfekte Milch beim abendlichen Melken.

Jede Kuh verbringt Zeit auf einer gegebenen Weide, nicht unbedingt allein. Finde aus Orten und Wegen die Zuckerweide mit minimaler Gesamtdistanz beim Läuten. Die Weiden sind ausreichend verbunden, sodass immer eine Lösung existiert.

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen, Kuhzahl $N$, Weidenzahl $P$ ($2\le P\le800$), Wegzahl $C$ ($1\le C\le1{,}450$). Eindeutige Nummern $1\ldots N$ für Kühe und $1\ldots P$ für Weiden.

• Zeilen $2\ldots N+1$: ganze Zahl, Weide einer Kuh; Kuh $i$ in Zeile $i+1$.

• Zeilen $N+2\ldots N+C+1$: drei ganze Zahlen mit Leerzeichen, zwei Weiden und Weglänge. Wege sind in beide Richtungen nutzbar, höchstens einer direkt pro Paar. Erste zwei Zahlen in $1\ldots P$, dritte in $1\ldots225$.

Ausgabe

• Zeile $1$: ganze Zahl, minimale Gesamtdistanz der Kühe zur Zuckerweide.

Beispiele

Eingabe 1

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

Ausgabe 1

8

Hinweis

Das Diagramm zeigt die Verbindungen geometrisch:

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

Bei Zucker auf Weide $4$ läuft Kuh $1$ insgesamt $3$ Einheiten, Kuh $2$ läuft $5$, Kuh $3$ läuft $0$, insgesamt $8$.

Autor der Aufgabe: Greg Galperin, 2001