== include(page="template/taskheader" task_id="ubuntzei") ==
Poveste şi cerinţă...
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.
h2. 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.
h2. Date de intrare
Fişierul de intrare $ubuntzei.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $ubuntzei.out$ ...
Fişierul de ieşire $ubuntzei.out$ va conţine o singură linie pe care va fi scris numărul natural $L$ reprezentând lungimea minimă căutată.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $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$.
h2. Exemplu
table(example). |_. ubuntzei.in |_. ubuntzei.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 5
1 2
1 2 1
1 3 1
2 3 1
2 4 4
3 4 2
| 4
|
h3. Explicaţie
...
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$.
== include(page="template/taskfooter" task_id="ubuntzei") ==
