Im Zentrum des Königreichs ICPC liegt ein großer runder See, und alle Städte wurden um den See herum errichtet, sodass sie einen Kreis bilden. Da sie alle nach demselben Stadtplan entwickelt wurden, sind sich die Städte sehr ähnlich. Sie haben genau dieselben U-Bahn-Netze. Einige ihrer Stationen sind zugleich Bahnhöfe für Hochgeschwindigkeitszüge zwischen Städten, die jeweils zwei entsprechende Stationen benachbarter Städte verbinden. Alle Bahnstrecken ermöglichen Verkehr in beide Richtungen zwischen zwei Endstationen, ohne Zwischenstationen.

Die Städte haben dieselbe Anzahl von U-Bahn-Stationen und U-Bahn-Strecken. In jeder Stadt sind die Stationen fortlaufend mit $0,1,2,\ldots$ nummeriert. Ob zwei Stationen innerhalb einer Stadt durch eine U-Bahn-Strecke verbunden sind, hängt nur von ihren Stationsnummern und nicht von der Stadt ab. Wenn eine Station $v$ in einer Stadt mit einer Station $u$ verbunden ist, gilt dies auch in allen anderen Städten. Die Entfernung zwischen den Stationen $v$ und $u$ ist in allen Städten gleich.

In allen Städten ist die Liste der Stationsnummern der Hochgeschwindigkeitsbahnhöfe genau gleich. Ist eine Station $s$ in einer Stadt ein Hochgeschwindigkeitsbahnhof, so gilt dies auch in allen anderen Städten. Alle Paare von Hochgeschwindigkeitsbahnhöfen mit derselben Stationsnummer in zwei benachbarten Städten sind durch eine Hochgeschwindigkeitsstrecke verbunden. Ist eine Station $s$ ein Ende einer solchen Strecke, so ist die Station $s$ in einer benachbarten Stadt das andere Ende. Es gibt keine weiteren Hochgeschwindigkeitsstrecken. Zwischen beliebigen zwei Stationen des Königreichs kann man mit einer oder mehreren U-Bahn- und/oder Hochgeschwindigkeitsverbindungen reisen.

Wegen finanzieller Schwierigkeiten in den letzten Jahren plant das Königreich, einige U-Bahn- und Hochgeschwindigkeitsverbindungen stillzulegen, um die Instandhaltungskosten des Bahnsystems zu senken. Die Instandhaltungskosten sind die Summe der Instandhaltungskosten aller U-Bahn-Strecken und Hochgeschwindigkeitsstrecken. Die Instandhaltungskosten einer U-Bahn-Strecke sind die Summe eines von der Stadt abhängigen Grundbetrags und eines zur Streckenlänge proportionalen Betrags. Die Instandhaltungskosten einer Hochgeschwindigkeitsstrecke hängen nur von den beiden durch sie verbundenen Städten ab.

Du sollst einen Plan zur Stilllegung einiger Strecken erstellen, der die gesamten Instandhaltungskosten minimiert. Natürlich müssen auch nach der Stilllegung alle Paare von Stationen im Königreich durch eine oder mehrere U-Bahn- und/oder Hochgeschwindigkeitsverbindungen verbunden bleiben.

Eingabe

Die Eingabe besteht aus einem einzelnen Testfall im folgenden Format.

$$ \begin{gathered} n\ m \\ v_1\ u_1\ d_1 \\ \vdots \\ v_m\ u_m\ d_m \\ l \\ a_0\ b_0 \\ \vdots \\ a_{l-1}\ b_{l-1} \\ r \\ s_1 \\ \vdots \\ s_r \end{gathered} $$

Dabei ist $n$ eine ganze Zahl mit $2\le n\le 10^4$ und gibt die Anzahl der U-Bahn-Stationen in einer Stadt an. Die Stationen jeder Stadt sind von $0$ bis $n-1$ nummeriert. $m$ ist eine ganze Zahl mit $1\le m\le 10^5$ und gibt die Anzahl der U-Bahn-Strecken in einer Stadt an. Die folgenden $m$ Zeilen beschreiben das U-Bahn-System einer Stadt. Die $i$-te dieser $m$ Zeilen enthält drei ganze Zahlen $v_i$, $u_i$ und $d_i$ mit $0\le v_i<n$, $0\le u_i<n$, $v_i\ne u_i$ und $1\le d_i\le 10^9$. Sie bedeuten, dass eine U-Bahn-Strecke die Stationen mit den Nummern $v_i$ und $u_i$ verbindet und der zur Streckenlänge proportionale Anteil ihrer Instandhaltungskosten $d_i$ beträgt. Zwischen zwei Stationen gibt es höchstens eine U-Bahn-Strecke. Alle U-Bahn-Stationen einer Stadt sind direkt oder indirekt über eine oder mehrere U-Bahn-Strecken miteinander verbunden.

$l$ in der nächsten Zeile ist eine ganze Zahl mit $3\le l\le 10^5$ und gibt die Anzahl der Städte im Königreich an. Die Städte sind von $0$ bis $l-1$ nummeriert, und Stadt $0$ wird auch Stadt $l$ genannt. Für jedes $0\le j\le l-1$ sind die Städte $j$ und $j+1$ benachbart. $a_j$ und $b_j$ in den folgenden $l$ Zeilen sind ganze Zahlen mit $1\le a_j\le 10^9$ und $1\le b_j\le 10^9$. $a_j$ sind die Instandhaltungskosten einer Hochgeschwindigkeitsstrecke zwischen den Städten $j$ und $j+1$. $b_j$ ist der Grundbetrag der Instandhaltungskosten einer U-Bahn-Strecke in Stadt $j$.

$r$ ist eine ganze Zahl mit $1\le r\le n$ und gibt die Anzahl der Hochgeschwindigkeitsbahnhöfe in jeder Stadt an. $s_1,s_2,\ldots,s_r$ sind die Stationsnummern der Hochgeschwindigkeitsbahnhöfe in jeder Stadt.

Ausgabe

Gib in einer einzigen Zeile die ganze Zahl aus, die die minimalen Instandhaltungskosten des Bahnsystems nach einer Stilllegung angibt, welche die Kosten minimiert und zugleich alle Stationen direkt oder indirekt miteinander verbunden hält.

Beispiele

Eingabe 1

2 1
0 1 3
3
6 1
4 2
5 3
1
1

Ausgabe 1

24

Eingabe 2

3 3
0 1 7
1 2 8
2 0 5
4
8 1
5 1
9 3
7 3
2
1
2

Ausgabe 2

76

Eingabe 3

5 8
0 1 1
2 1 2
4 0 5
3 4 7
3 2 8
0 2 4
4 1 3
2 4 6
6
3 2
9 3
7 1
5 3
3 2
5 2
4
0
2
3
4

Ausgabe 3

120