Zadanie

Iste ju poznáte

Počet bodov: 70

A ak nie, odporúčame (po súťaži) vychutnať si legendárnu meme pesničku of times of past: https://www.youtube.com/watch?v=FuOhQZP821o

croaking sounds

Idem si sústredkovať, na Oravský Podzámok.
Meškám, a tak riskujem, prechádzam cez Pezinok.
Býva tam to strašidlo, utiecť mu len ťažko,
jedáva účastníkov sústrediek a volá sa Jožko.

Jožko z Pezinku, z vlaku sa už plíži.
Jožko z Pezinku, k sústredku sa blíži.
Jožko z Pezinku, už si zuby brúsi.
Jožka z Pezinku, odstrašiť ty musíš.
Jožka z Pezinku, koho by to napadlo,
desí len a iba, motorové čerpadlo.

croaking sounds

Klikli ste na úlohu, ktorú teraz čítate.
Spísal ju tu Hodobox, zverejnil ju v Zenite.
Každého dosť chytrého, čo Jožka odoženie
za odmenu dostane, 70 bodov a od testovača overenie.

Chatiek na sústredku, \(N\) ich jest.
Spája ich \(M\) rôznych, ováhovaných ciest.
Navyše už máme \(C\)-krát čerpádlá zakúpené
a \(K\) chatiek, na ktoré Jožko vplížiť sa má, postupne naplánované.
Čerpadlá viete, za cenu manuálnej práce, presúvať po cestách.
Odstrašte vždy Jožka tak, aby čo najmenej to malo stáť.

croaking sounds

Úloha

Máme \(N\) chatiek očíslovaných od \(1\) po \(N\), spajáných \(M\) cestami a \(C\) motorových čerpadiel.

Čerpadlá začínajú v chatkách s číslami \(1\) až \(C\).

Navyše máme Jožkov plán - \(K\) chatiek, do ktorých sa postupne, v zadanom poradí plánuje vplížiť.

Keď sa Jožko plíži do chatky, musí v nej byť motorové čerpadlo, aby ho odstrašilo.

Ak tam momentálne nie je, musíme ho dovliecť z niektorej chatky, v ktorej práve je.

To nás stojí súčet dĺžok ciest, cez ktoré sme museli čerpadlo vláčiť.

Nájdite najmenšiu cenu, za ktorú vieme Jožka odstrašiť postupne od všetkých chatiek, ktoré má naplánované napadnúť.

Vstup a Výstup

V prvom riadku vstupu sú tri čísla \(N\), \(M\) a \(C\) - počet chatiek, ciest a čerpadiel.

V nasledujúcich \(M\) riadkoch sú tri čísla \(a_i b_i d_i\), označujúce cestu medzi chatkami \(a_i\) a \(b_i\) dlhú \(d_i\). Medzi každými dvoma chatkami vždy existuje nejaká postupnosť ciest.

V \(M+2\)hom riadku je číslo \(K\) - počet chatiek, na ktoré Jožko zaútočí.

V \(M+3\)ťom riadku je \(K\) čísel chatiek \(k_i\) v poradí, v akom na ne Jožko zaútočí.

Vypíšte najmenšiu cenu, za ktorú vieme sústredko obrániť proti Jožkovi.

Platí \(1 \leq C \leq N \leq 30\), \(1 \leq C \leq 6\), \(N-1 \leq M \leq N(N-1)/2\), a \(1 \leq K \leq 50\).

Pre cesty platí \(1 \leq a_i, b_i \leq N\), \(a_i \neq b_i\) a \(1 \leq d_i \leq 2\,000\,000\), pričom graf je spojený a jednoduchý.

Nakoniec samozrejme platí \(1 \leq k_i \leq N\).

Sú štyri sady vstupov. V prvých troch platí \(N \leq 20\). V prvej navyše \(C=1\). V druhej zasa \(C=2\).

Príklad

Input:

3 2 1
1 2 10
2 3 20
4
1 2 3 1

Output:

60

Jožko sa priplíži k prvej chatke, v ktorej začína a tam ho odstraší čerpadlo. Potom ho za cenu 10 odvláčíme do chatky 2, odstrašíme Jožka, za cenu 20 ho dotiahneme chatky 3 na ďaľšie odstrašenie a nakoniec ho cez obe cesty za cenu 30 rýchlo vrátime späť do prvej chatky, na Jožkove finálne vplíženie.

Input:

4 4 2
1 3 10
2 3 11
1 4 20
2 4 22
2
3 4

Output:

31

Odvlečieme čerpadlo z prvej chatky do štvrtej a z druhej do tretej. Stojí nás to 20+11=31

Input:

5 4 2
1 3 5
2 3 4
3 5 100
2 4 1
4
3 4 5 1

Output:

114

Input:

7 10 3
1 2 123
3 1 444
4 7 1234
6 3 121
5 2 192
6 5 222
6 7 311
4 2 244
7 3 221
3 2 98
15
1 2 3 4 5 6 7 5 2 3 1 4 2 3 1

Output:

1723