ubuntzei

Trei ubuntzei au hotărât ca anul acesta să petreacă ziua de 1 Mai pe malul Mării Negre împreună cu prietenii lor, motiv pentru care au pus la cale o excursie pe un traseu care să plece din oraşul lor Cluj-Napoca spre Vama Veche, unde nisipul îi aşteaptă.

În ţara ubuntzeilor există $N$ localităţi, numerotate de la $1$ la $N$, legate între ele prin $M$ şosele bidirecţionale de diferite lungimi. Localitatea de plecare a ubuntzeilor, oraşul Cluj-Napoca, este numerotată cu $1$, iar localitatea destinaţie, Vama Veche, cu $N$. Între oricare două localităţi există cel mult o şosea. Fiecare şosea uneşte două localităţi distincte şi se poate călători între oricare două localităţi circulând numai pe şosele.

Prietenii ubuntzeilor locuiesc în $K$ localităţi distincte, diferite de Cluj-Napoca şi Vama Veche. Pentru a nu călători singuri, cei trei ubuntzei vor să treacă prin cele $K$ localităţi în care locuiesc prietenii lor, şi apoi, împreună cu aceştia, să-şi continue excursia către mare.

Nerăbdători să ajungă cât mai repede la destinaţie, ubuntzeii s-au hotărât să îşi stabilească un traseu de lungime minimă care să treacă prin toate cele $K$ localităţi.

Cerinţă

Scrieţi un program care să determine, pentru ubuntzei, lungimea minimă $L$ a unui traseu de la Cluj-Napoca la Vama Veche ce trece prin toate cele $K$ localităţi.

Date de intrare

Prima linie a fişierului de intrare ubuntzei.in conţine două numere naturale $N\ M$, separate printr-un spaţiu, cu semnificaţia din enunţ. A doua linie a fişierului conţine $K + 1$ numere naturale distincte: $K\ C_1\ C_2\ ...\ C_K$, separate prin câte un spaţiu, $K$ având semnificaţia din enunţ iar $C_1, C_2, ..., C_K$ reprezentând cele $K$ localităţi în care locuiesc prietenii. Fiecare din următoarele $M$ linii conţine câte trei numere naturale $x\ y\ z$, separate prin câte un spaţiu, reprezentând o şosea care leagă localitatea $x$ de localitatea $y$ şi are lungimea $z$.

Date de ieşire

Fişierul de ieşire ubuntzei.out va conţine numărul natural $L$ reprezentând lungimea minimă căutată.

Restricţii şi precizări

• $1 ≤ N ≤ 2\ 000$
• $1 ≤ M ≤ 10\ 000$
• $0 ≤ K ≤ \min\{15, N - 2\}$
• $2 ≤ C_1, C_2, ..., C_K ≤ N - 1$
• Traseul poate trece de mai multe ori prin oricare localitate.
• Costul unei muchii va fi cuprins între $1$ şi $10^5$.
• Pentru primele $20\%$ din teste $K = 0$.
• Pentru primele $50\%$ din teste $K ≤ 10$.
• Pentru primele $70\%$ din teste $N ≤ 200$.

Exemplu

ubuntzei.in

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

ubuntzei.out

4

Explicații

Există un singur traseu de lungime minimă de la localitatea $1$ la localitatea $4$ şi care trece prin localitatea $2$, şi anume: $[1,2,3,4]$. Lungimea $L$ a acestui traseu este $4$.