Descripción del problema
En el Reino JOI hay $N$ pueblos, y entre ellos están conectados mediante $M$ carreteras transitables en ambos sentidos. En $K$ pueblos hay centros comerciales, y los ciudadanos viajan por las carreteras hasta alguno de esos pueblos para hacer sus compras.
Dependiendo de la ubicación de una casa, puede ser necesario recorrer una larga distancia para ir de compras, lo cual resulta muy incómodo. Para conocer esta situación real, el Rey decidió investigar qué tan larga puede llegar a ser la distancia más corta hasta un pueblo con centro comercial dependiendo de la ubicación de la casa. Dado que una casa también puede construirse en mitad de una carretera (véase la explicación del Ejemplo $1$), esta investigación es muy difícil. Por ello, el Rey te ha pedido a ti, un excelente programador, que escribas un programa que realice la investigación.
Dada la información de las carreteras y la información de los pueblos con centro comercial, escribe un programa para hallar la distancia desde los pueblos con centro comercial hasta el punto más lejano situado sobre una carretera (incluyendo los extremos). Puedes ignorar la distancia necesaria para desplazarse dentro de un pueblo.
Entrada
Lee la siguiente entrada desde la Entrada Estándar:
- La $1$-ra línea contiene los enteros $N, M, K$ separados por espacios. $N$ representa el número de pueblos del Reino JOI, $M$ representa el número de carreteras del Reino JOI y $K$ representa el número de pueblos con centro comercial, respectivamente. Los pueblos están numerados $1, 2, \dots, N$.
- Las siguientes $M$ líneas representan la información de las carreteras. La línea $(i + 1)$ ($1 \le i \le M$) contiene los enteros $a_i, b_i, l_i$ ($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$) separados por espacios. Esto significa que la $i$-ésima carretera conecta el pueblo $a_i$ y el pueblo $b_i$, y tiene longitud $l_i$. Los dos extremos de una carretera nunca son el mismo pueblo. Además, para cualesquiera $2$ pueblos $p, q$, nunca existen $2$ o más carreteras que conecten $p$ y $q$. Es posible ir de cualquier pueblo a cualquier otro siguiendo algunas carreteras.
- Las siguientes $K$ líneas representan la información de los centros comerciales. La línea $(i + M + 1)$ ($1 \le i \le K$) contiene $1$ entero $s_i$ ($1 \le s_i \le N$). Esto significa que hay un centro comercial en el pueblo $s_i$. Un mismo valor nunca aparece $2$ o más veces entre $s_1, \dots, s_K$.
Salida
Imprime en la Salida Estándar $1$ entero: el valor máximo de la distancia más corta a un pueblo con centro comercial, redondeado al entero más cercano.
Ejemplo
Ejemplo 1
Entrada
3 3 1 1 2 1 2 3 1 3 1 1 1
Salida
2
Explicación
El ejemplo de entrada $1$ representa los pueblos que se muestran en la siguiente figura. Las longitudes de las carreteras son todas $1$. Solo hay centro comercial en el pueblo $1$.
El punto más lejano a un pueblo con centro comercial es el punto de la carretera que conecta el pueblo $2$ y el pueblo $3$ situado a una distancia de $0.5$ del pueblo $2$, y su distancia al pueblo con centro comercial es $1.5$. Por lo tanto, se imprime $2$, que es el valor redondeado.
Ejemplo 2
Entrada
4 5 2 1 2 4 1 3 1 2 3 2 2 4 2 3 4 1 2 4
Salida
3
Restricciones
- $2 \le N \le 3000$: el número de pueblos del Reino JOI.
- $1 \le M \le 100000 = 10^5$: el número de carreteras del Reino JOI.
- $1 \le K \le N$: el número de pueblos con centro comercial.
- $1 \le l_i \le 1000$: la longitud de la $i$-ésima carretera.
Criterios de calificación
- Para los datos de prueba que valen el $40\%$ de la puntuación total, se cumple $K = 1$.