Zadanie

Jazdci štrikujú

Počet bodov: 75

Jarka mala nedávno narodeniny. Jazdci jej nič nedali a teraz sú z toho smutní, tak sa rozhodli, že jej aspoň uštrikujú šál.

Problém je ale v tom, že každý z jazdcov má len jednu ruku dostatočne šikovnú na štrikovanie. Musia sa teda nejakí dvaja stretnúť.

Na vstupe je daný počet jazdcov a popis mesta, v ktorom sú. Mesto je tvorené \(n\) lokalitami, ktoré sú medzi sebou poprepájané sieťou \(m\) obojsmerných ulíc. Rôzne ulice môžu mať rôznu dĺžku.

Všetci jazdci sú rovnako rýchli: hýbu sa tempom 10 metrov za minútu.

Vypočítajte najkratší možný čas, za ktorý sa vedia dvaja jazdci stretnúť.

Vstup a výstup

V prvom riadku vstupu sú kladné celé čísla \(z\), \(n\) a \(m\). Žiadne z týchto čísel neprekročí \(100\,000\). Jazdci sú aspoň dvaja. V prvej sade navyše platí že žiadne z týchto čísel neprekročí \(10\).

Lokality v meste majú čísla od 1 po \(n\). V každom z nasledujúcich \(z\) riadkov je jedno číslo lokality, udávajúce miesto, kde začína jeden zo \(z\) jazdcov.

Zvyšok vstupu tvorí popis ulíc. V každom riadku sú dve rôzne čísla lokalít, ktoré daná ulica spája, a kladné celé číslo udávajúce jej dĺžku v metroch. Dĺžka žiadnej ulice neprekročí 5000.

V každom vstupe bude existovať aspoň jedna dvojica jazdcov, ktorí sa vedia stretnúť.

Vypíšte jeden riadok a v ňom jedno celé číslo: najmenší čas v sekundách, po ktorom sa vedia dvaja jazdci stretnúť.

Príklady

Input:

2 2 1
1
2
1 2 5

Output:

15

Dvaja jazdci idú proti sebe po ulici, stretnú sa po 15 sekundách.

Input:

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

Output:

12

Hociktorá dvojica jazdcov sa vie stretnúť v strede ulice spájajúcej ich začiatočné lokality.

Input:

2 3 3
1
2
1 2 9
3 2 5
1 3 3

Output:

24

Najvýhodnejšie miesto stretnutia leží na ulici spájajúcej lokality 2 a 3, vo vzdialenosti 1 meter od lokality 3.