Lýsing á verkefni

Í JOI-konungsríkinu eru $N$ bæir og á milli þeirra liggja $M$ tvístefnu vegir. Í $K$ bæjum eru verslunarmiðstöðvar og íbúarnir ferðast eftir vegunum til eins af þessum bæjum til að versla.

Eftir því hvar hús er staðsett getur þurft að fara langa leið til að komast í búð, sem er mjög óþægilegt. Til að átta sig á þessum raunveruleika ákvað konungurinn að kanna hversu löng stysta vegalengdin í bæ með verslunarmiðstöð getur orðið eftir staðsetningu húss. Þar sem hús geta einnig verið byggð á miðjum vegi (sjá útskýringu á Dæmi $1$) er þessi könnun mjög erfið. Þess vegna bað konungurinn þig, afbragðs forritara, um að skrifa forrit sem framkvæmir könnunina.

Gefnar eru upplýsingar um vegina og upplýsingar um bæina sem eru með verslunarmiðstöð; skrifið forrit sem finnur vegalengdina frá bæjunum með verslunarmiðstöð að fjarlægasta punkti á vegi (endapunktar meðtaldir). Hægt er að líta fram hjá vegalengdinni sem fer í að ferðast innan bæjar.

Inntak

Lesið eftirfarandi inntak úr staðalinntaki:

• Í $1$. línu eru heiltölurnar $N, M, K$ aðskildar með bilum. $N$ táknar fjölda bæja í JOI-konungsríkinu, $M$ táknar fjölda vega í JOI-konungsríkinu og $K$ táknar fjölda bæja með verslunarmiðstöð. Bæirnir eru númeraðir $1, 2, \dots, N$.
• Næstu $M$ línur lýsa vegunum. Lína $(i + 1)$ ($1 \le i \le M$) inniheldur heiltölurnar $a_i, b_i, l_i$ ($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$) aðskildar með bilum. Þetta þýðir að $i$-ti vegurinn tengir saman bæ $a_i$ og bæ $b_i$ og hefur lengdina $l_i$. Báðir endar vegar eru aldrei sami bærinn. Auk þess, fyrir hvaða $2$ bæi $p, q$ sem er, eru aldrei $2$ eða fleiri vegir sem tengja $p$ og $q$. Hægt er að komast frá hvaða bæ sem er til hvaða bæjar sem er með því að fara eftir nokkrum vegum.
• Næstu $K$ línur lýsa verslunarmiðstöðvunum. Lína $(i + M + 1)$ ($1 \le i \le K$) inniheldur $1$ heiltölu $s_i$ ($1 \le s_i \le N$). Þetta þýðir að verslunarmiðstöð sé í bæ $s_i$. Sama gildið kemur aldrei fyrir $2$ sinnum eða oftar meðal $s_1, \dots, s_K$.

Úttak

Skrifið út $1$ heiltölu í staðalúttak: hámarksgildi stystu vegalengdar í bæ með verslunarmiðstöð, námundað að næstu heiltölu.

Dæmi

Dæmi 1

Inntak

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

Úttak

2

Útskýring

Inntaksdæmi $1$ lýsir bæjunum sem sýndir eru á myndinni hér að neðan. Lengdir allra vega eru $1$. Verslunarmiðstöð er aðeins í bæ $1$.

Punkturinn sem er lengst frá bæ með verslunarmiðstöð er punkturinn á veginum sem tengir bæ $2$ og bæ $3$, í fjarlægð $0.5$ frá bæ $2$, og fjarlægð hans í bæinn með verslunarmiðstöðina er $1.5$. Því er námundaða gildið $2$ prentað út.

Dæmi 2

Inntak

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

Úttak

3

Takmarkanir

• $2 \le N \le 3000$: fjöldi bæja í JOI-konungsríkinu.
• $1 \le M \le 100000 = 10^5$: fjöldi vega í JOI-konungsríkinu.
• $1 \le K \le N$: fjöldi bæja með verslunarmiðstöð.
• $1 \le l_i \le 1000$: lengd $i$-ta vegarins.

Stigagjöf

• Fyrir prófunargögn sem gilda $40\%$ af heildarstigum gildir $K = 1$.