Tehtävänanto

JOI-kuningaskunnassa on $N$ kaupunkia, ja niitä yhdistää $M$ kaksisuuntaista tietä. $K$ kaupungissa on ostoskeskus, ja kansalaiset kulkevat teitä pitkin johonkin näistä kaupungeista tekemään ostoksia.

Talon sijainnista riippuen ostoksille pääsemiseksi voi joutua kulkemaan pitkän matkan, mikä on erittäin hankalaa. Selvittääkseen todellisen tilanteen kuningas päätti tutkia, kuinka pitkäksi lyhin etäisyys ostoskeskuksen sisältävään kaupunkiin voi talon sijainnista riippuen kasvaa. Koska talo voidaan rakentaa myös keskelle tietä (katso Esimerkin $1$ selitys), tämä selvitys on hyvin vaikea. Niinpä kuningas pyysi sinua, taitavaa ohjelmoijaa, kirjoittamaan ohjelman, joka tekee tämän selvityksen.

Kun teiden tiedot ja ostoskeskuksen sisältävien kaupunkien tiedot annetaan, kirjoita ohjelma, joka etsii etäisyyden ostoskeskuksen sisältävistä kaupungeista kaukaisimpaan tiellä olevaan pisteeseen (mukaan lukien tien päätepisteet). Kaupungin sisällä liikkumiseen kuluvaa matkaa ei tarvitse huomioida.

Syöte

Lue seuraava syöte vakiosyötteestä:

• $1$. rivillä on välilyönnein erotetut kokonaisluvut $N, M, K$. $N$ ilmaisee JOI-kuningaskunnan kaupunkien lukumäärän, $M$ JOI-kuningaskunnan teiden lukumäärän ja $K$ niiden kaupunkien lukumäärän, joissa on ostoskeskus. Kaupungit on numeroitu $1, 2, \dots, N$.
• Seuraavat $M$ riviä kuvaavat teiden tiedot. $(i + 1)$:nnellä rivillä ($1 \le i \le M$) on välilyönnein erotetut kokonaisluvut $a_i, b_i, l_i$ ($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$). Tämä tarkoittaa, että $i$-s tie yhdistää kaupungin $a_i$ ja kaupungin $b_i$ ja sen pituus on $l_i$. Tien molemmat päät eivät koskaan ole sama kaupunki. Lisäksi millekään $2$ kaupungille $p, q$ ei ole $2$ tai useampaa tietä, jotka yhdistävät $p$:n ja $q$:n. Mistä tahansa kaupungista pääsee mihin tahansa kaupunkiin kulkemalla joitakin teitä pitkin.
• Seuraavat $K$ riviä kuvaavat ostoskeskusten tiedot. $(i + M + 1)$:nnellä rivillä ($1 \le i \le K$) on $1$ kokonaisluku $s_i$ ($1 \le s_i \le N$). Tämä tarkoittaa, että kaupungissa $s_i$ on ostoskeskus. Lukujen $s_1, \dots, s_K$ joukossa sama arvo ei esiinny $2$ tai useampaa kertaa.

Tuloste

Tulosta vakiotulosteeseen $1$ kokonaisluku: ostoskeskuksen sisältävään kaupunkiin olevan lyhimmän etäisyyden maksimiarvo pyöristettynä lähimpään kokonaislukuun (puolikkaat pyöristetään ylöspäin).

Esimerkki

Esimerkki 1

Syöte

3 3 1
1 2 1
2 3 1
3 1 1
1

Tuloste

2

Selitys

Syöteesimerkki $1$ kuvaa alla olevan kuvan mukaisia kaupunkeja. Kaikkien teiden pituus on $1$. Ostoskeskus on vain kaupungissa $1$.

Kauimpana ostoskeskuksen sisältävästä kaupungista oleva piste sijaitsee kaupungin $2$ ja kaupungin $3$ yhdistävällä tiellä etäisyydellä $0.5$ kaupungista $2$, ja sen etäisyys ostoskeskuksen sisältävään kaupunkiin on $1.5$. Siispä tulostetaan pyöristetty arvo $2$.

Esimerkki 2

Syöte

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

Tuloste

3

Rajoitukset

• $2 \le N \le 3000$: JOI-kuningaskunnan kaupunkien lukumäärä.
• $1 \le M \le 100000 = 10^5$: JOI-kuningaskunnan teiden lukumäärä.
• $1 \le K \le N$: ostoskeskuksen sisältävien kaupunkien lukumäärä.
• $1 \le l_i \le 1000$: $i$-nnen tien pituus.

Pisteytys

• Testitapauksissa, joiden arvo on $40\%$ kokonaispisteistä, pätee $K = 1$.