Shopping Malls

A country has $N$ cities connected by $M$ bidirectional roads. Exactly $K$ of these cities contain a shopping mall, and residents travel along the roads to a city with a mall in order to shop.

A house may sit inside a city, or at any point along a road. The distance from a house to the malls is defined as the shortest distance from that house to the nearest mall. People always take a shortest path, and moving within a city takes $0$ time.

Given the roads and the cities that contain a mall, write a program that finds the distance to the house that is farthest from the malls — that is, the maximum, over every possible house location, of the shortest distance from that house to the nearest shopping mall.

The first line contains the number of cities $N$, the number of roads $M$, and the number of cities that contain a mall $K$. Cities are numbered from $1$ to $N$. ($2 \le N \le 3000$, $1 \le M \le 10^5$, $1 \le K \le N$)

Each of the next $M$ lines contains a road $a$, $b$, $l$: a road of length $l$ ($1 \le l \le 1000$) connecting city $a$ and city $b$. $a$ and $b$ are different, and at most one road connects any pair of cities. Every city is reachable from every other city (the graph is connected).

Each of the next $K$ lines contains the number of one city that has a mall, one per line; these numbers are distinct.

Print the distance to the house that is farthest from the malls, rounded to the nearest integer (round halves up).

Suppose a house lies on the road of length $l$ between city $a$ and city $b$, at distance $x$ ($0 \le x \le l$) from city $a$. Then the distance from this house to the nearest mall is $\min(d_a + x,\; d_b + (l - x))$, where $d_v$ is the shortest distance from city $v$ to the nearest mall. The point that maximizes this value gives a distance of $\dfrac{d_a + d_b + l}{2}$.

In the first example, every road has length $1$ and the only mall is in city $1$. The house farthest from the mall lies on the road between city $2$ and city $3$, at distance $0.5$ from city $2$; its distance to the mall is $1.5$, which rounds to $2$.