Mirror - Future for Future XI-XII - 2024 | Lăptika

Andi este un băiat buclucaș! Obosit după proba de națională, a luat ciocolata Lăptika, fără a mai declara în scris acest fapt. Acum toată comisia este pe urmele lui! Campusul este compus din $N$ clădiri, numerotate de la $1$ la $N$, iar între acestea se află $M$ drumuri directe, bidirecționale, de un anumit cost. $K$ dintre acele clădiri reprezintă centre de examinare, din care comisia va pleca în căutarea lui Andi. Se definește distanța dintre două cladiri, $A$ și $B$, ca fiind suma minimă a costurilor drumurilor necesare pentru a ajunge la clădirea $B$, plecând din clădirea $A$.

Cerință

Cunoscând forma campusului, ajutați-l pe Rara să găsească clădirea cea mai îndepărtată de oricare centru de examinare, pentru a-și putea salva prietenul mai mic.

Date de intrare

Fișierul de intrare laptika.in conține:

• Pe prima linie, numerele naturale $N$, $M$ şi $K$, separate printr-un spațiu;
• Pe a doua linie, se vor afla indicii celor $K$ centre de examinare, numere distincte, separate printr-un spaţiu;
• Pe următoarele $M$ linii, câte $3$ numere de forma $\{\ A, B, C \ \}$, care reprezintă un drum direct între nodurile $A$ și $B$, de costul $C$.

Date de ieșire

Pe prima linie a fișierului de ieșire laptika.out se va scrie numărul de ordine al celei mai îndepărtate clădiri de oricare centru de examinare și distanța minimă până la aceasta, separate printr-un spațiu.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$;
• $N-1 \leq M \leq min(N \cdot (N-1)/2, \ 500 \ 000)$;
• $1 \leq K \leq N$;
• $1 \leq A, B \leq N, \ A\neq B, \ 1 \leq C \leq 1 \ 000$;
• Campusul este bine gândit, se poate ajunge din fiecare clădire în oricare alta;
• Dacă există mai multe clădiri convenabile, afișați-o pe cea cu indicele cel mai mic;
• Poate exista mai mult de un drum direct între $2$ clădiri.

Exemplu

laptika.in

10 13 4
2 5 6 8
2 1 8
2 4 5
2 7 2
1 4 13
1 6 2
1 7 4
7 5 5
5 8 1
5 10 8
6 3 3
6 9 10
6 8 2
8 9 8

laptika.out

9 8

Explicație

Atât clădirea 9, cât și clădirea 10 sunt cele mai indepărtate și se află la distanța 8 față de cel mai apropiat centru de examinare (8, respectiv 5). Cum 9 este mai mic decat 10, acesta va fi numărul afișat.