P5845 [IOI 2011] crocodile

After exploring the mysterious underground crocodile palace, archaeologist Benjamas needs to find a way to escape. This underground palace contains $N$ caves and $M$ bidirectional tunnels. Each tunnel connects a pair of different caves, and there is at most one tunnel between any two caves. Traveling along different tunnels may take different amounts of time. Among the $N$ caves, there are $K$ exit caves, and Benjamas can escape from any exit cave. Benjamas starts from cave $0$ and wants to reach an exit cave as quickly as possible. The crocodile guard wants to stop Benjamas from escaping the palace. It can use a mechanism to block any one tunnel (at any moment, it can block only one tunnel). That is, whenever the guard blocks a new tunnel, the previously blocked tunnel will be opened. Benjamas’s escape process can be described as follows: each time she tries to leave a cave, the crocodile guard will block one tunnel connected to that cave. Benjamas can only choose an unblocked tunnel to go to the next cave. Once Benjamas enters a tunnel, the guard cannot block that tunnel before she reaches the other end. When Benjamas arrives at the next cave, the guard may choose to block another tunnel (which may be the tunnel Benjamas just used). Benjamas needs to design an escape plan. More precisely, she wants a sequence of instructions that tells her how to escape. Let $A$ be a cave. If $A$ is an exit cave, Benjamas can escape immediately. Otherwise, for cave $A$, the instruction is one of the following forms: - At cave $A$, first try to take the tunnel to cave $B$. If that tunnel is blocked, then take another tunnel to cave $C$. - Ignore cave $A$; according to the escape plan, cave $A$ will never be reached. Note: The testdata guarantees that no matter how the crocodile guard blocks tunnels, there always exists a good escape plan that guarantees Benjamas can reach an exit cave in finite time. Among all escape plans, the time used by the escape plan with the minimum time in the worst case is defined as $T$.

The first line contains three integers $N$, $M$, $K$. The next $M$ lines each contain three integers, describing the two endpoints of an undirected edge and its length (no multiple edges). The next line contains $K$ integers, describing the exit caves.

Output one integer, the minimum time $T$.

**Constraints** For $100\%$ of the testdata, $3 \le N \le 10^5$, $2 \le M \le 10^6$. The testdata guarantees that $T$ exists, and $T \le 10^9$. Translated by ChatGPT 5