Problembeskrivelse

I kongeriket JOI er det $N$ byer, og mellom dem går det $M$ toveis veier. I $K$ av byene er det et kjøpesenter, og innbyggerne reiser langs veiene til en av disse byene for å handle.

Avhengig av hvor et hus ligger, kan det være nødvendig å reise langt for å dra på handletur, noe som er svært upraktisk. For å få oversikt over denne situasjonen bestemte kongen seg for å undersøke hvor lang den korteste avstanden til en by med kjøpesenter kan bli, avhengig av hvor huset ligger. Siden hus også kan bygges midt langs en vei (se forklaringen til Eksempel $1$), er denne undersøkelsen svært krevende. Derfor har kongen bedt deg, en dyktig programmerer, om å skrive et program som utfører undersøkelsen.

Gitt informasjonen om veiene og informasjonen om byene med kjøpesenter, skriv et program som finner avstanden fra byene med kjøpesenter til det punktet på en vei (inkludert endepunktene) som ligger lengst unna. Du kan se bort fra avstanden det tar å bevege seg inne i en by.

Inndata

Les følgende inndata fra standard inndata:

• Den $1$. linjen inneholder heltallene $N, M, K$ atskilt med mellomrom. $N$ angir antallet byer i kongeriket JOI, $M$ angir antallet veier i kongeriket JOI, og $K$ angir antallet byer som har et kjøpesenter. Byene er nummerert $1, 2, \dots, N$.
• De neste $M$ linjene beskriver veiene. Den $(i + 1)$-te linjen ($1 \le i \le M$) inneholder heltallene $a_i, b_i, l_i$ ($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$) atskilt med mellomrom. Dette betyr at den $i$-te veien forbinder by $a_i$ og by $b_i$, og har lengde $l_i$. Begge endene av en vei er aldri den samme byen. Videre finnes det for enhver一对 av $2$ byer $p, q$ aldri $2$ eller flere veier som forbinder $p$ og $q$. Det er mulig å reise fra enhver by til enhver annen by ved å følge noen veier.
• De neste $K$ linjene beskriver kjøpesentrene. Den $(i + M + 1)$-te linjen ($1 \le i \le K$) inneholder $1$ heltall $s_i$ ($1 \le s_i \le N$). Dette betyr at det ligger et kjøpesenter i by $s_i$. Den samme verdien forekommer aldri $2$ eller flere ganger blant $s_1, \dots, s_K$.

Utdata

Skriv ut $1$ heltall til standard utdata: den maksimale verdien av den korteste avstanden til en by med kjøpesenter, avrundet til nærmeste heltall.

Eksempel

Eksempel 1

Inndata

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

Utdata

2

Forklaring

Eksempel $1$ representerer byene som vist i figuren nedenfor. Lengdene på alle veiene er $1$. Det er kun kjøpesenter i by $1$.

Det punktet som ligger lengst unna en by med kjøpesenter, er punktet på veien mellom by $2$ og by $3$ i avstand $0.5$ fra by $2$, og avstanden derfra til byen med kjøpesenter er $1.5$. Derfor skrives den avrundede verdien $2$ ut.

Eksempel 2

Inndata

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

Utdata

3

Begrensninger

• $2 \le N \le 3000$: antallet byer i kongeriket JOI.
• $1 \le M \le 100000 = 10^5$: antallet veier i kongeriket JOI.
• $1 \le K \le N$: antallet byer med kjøpesenter.
• $1 \le l_i \le 1000$: lengden på den $i$-te veien.

Poengberegning

• For testdata verdt $40\%$ av total poengsum gjelder $K = 1$.