Fişierul intrare/ieşire:	posta2.in, posta2.out	Sursă	ONI 2011, clasele 11-12
Autor	Cosmin-Mihai Tutunaru	Adăugată de	Gabriel Bitis •gabitzish1
Timp execuţie pe test	0.1 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Posta2

Într-o ţară minunată, cele N oraşe sunt legate între ele prin N-1 şosele astfel încât din fiecare oraş se poate ajunge în oricare alt oraş. Se ştie costul benzinei necesare pentru parcurgerea fiecărei şosele şi costul de intrare în fiecare oraş. Ţirbi, managerul poştei, trebuie să aleagă sediul poştei, ştiind că va avea de livrat colete în M oraşe precizate, plecând de la sediul poştei şi revenind după livrarea coletelor tot la sediul poştei. El trebuie să aleagă sediul astfel încât să minimizeze costul transporturilor, ţinând cont că poşta va întocmi un contract cu guvernul prin care va fi scutită de:

• toate taxele de intrare din oraşul în care îşi stabileşte sediul;
• prima intrare în oricare alt oraş, iar pentru restul intrărilor se plăteşte taxa.

Cerinţă

Cunoscând numărul de oraşe, şoselele, taxele de intrare în fiecare oraş şi cele M oraşe în care se livrează coletele, ajutaţi-l pe Ţirbi să calculeze costul minim necesar pentru livrarea comenzilor.

Date de intrare

Fişierul de intrare posta2.in conţine pe prima linie două numere naturale N şi M separate printr-un spaţiu, cu semnificaţia din enunţ. Pe următoarele N-1 linii se vor afla câte trei numere x, y, z, separate prin câte un spaţiu, cu semnificaţia că există şosea de la oraşul x la oraşul y având costul z. Pe următoarea linie se află N numere naturale reprezentând taxa de intrare din fiecare oraş. Ultima linie conţine M numere naturale reprezentând oraşele în care poşta trebuie să livreze comenzi.

Date de ieşire

În fişierul de ieşire posta2.out conţine costul minim al unui transport.

Restricţii

• 2 ≤ M ≤ N ≤ 100.000
• Toate taxele şi costurile sunt numere naturale strict pozitive mai mici sau egale cu 100.000.
• Maşina poate trece prin oricare oraş sau pe orice şosea de oricâte ori.
• Oraşele în care livrează comenzi sunt distincte.
• Pentru 10% din teste M ≤ 3
• Pentru 30% din teste N ≤ 1.000

Exemplu

Explicaţie

Se va alege sediul în oraşul 1 şi se va parcurge următorul traseu:
1 → 2 → 4 → 2 → 1 → 5 → 6 → 5 → 1
Costul benzinei este 26
Costul taxelor este 2 (oraşul 2 + oraşul 5)
În oraşele 4 şi 6 nu se plăteşte taxă deoarece se intră o singură dată.

Cum se trimit solutii?