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 C1 C2 ... CK, separate prin câte un spaţiu, K având semnificaţia din enunţ, iar C1 C2 ... CK reprezentând cele K localităţi în care locuiesc prietenii. Fiecare dintre 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 o singură linie pe care va fi scris numărul natural L reprezentând lungimea minimă căutată.
Restricţii
• 1 ≤ N ≤ 2 000
• 1 ≤ M ≤ 10 000
• 0 ≤ K ≤ min{15, N – 2}
• 2 ≤ C1, C2,.. CK ≤ N – 1
• Traseul poate trece de mai multe ori prin oricare localitate.
• Costul unei muchii va fi cuprins între 1 şi 105.
• Pentru primele 20% din teste K = 0.
• Pentru primele 50% din teste K ≤ 10.
• Pentru primele 70% din teste N ≤ 200.
Exemple
ubuntzei.in
ubuntzei.out
Explicaţii
4 5
1 2
1 2 1
1 3 1
2 3 1
2 4 4
3 4 2
4
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.