Two-Step Shortest Path 4

Seojun was very happy to receive a world map from his father as a birthday present. He wants to write a program that finds shortest paths on the world map to express his gratitude to his father. The world map is an undirected graph whose vertices are cities and whose edges are roads between cities, and the length of a road is the weight of the edge. Find the shortest distance from the start vertex $X$ to the destination vertex $Z$ that passes through all $P$ intermediate vertices.

The first line gives the number of vertices $N$ ($10 \le N \le 100{,}000$) and the number of edges $M$ ($10 \le M \le 300{,}000$).

The next $M$ lines give edge information u v w, meaning a bidirectional road between city $u$ and city $v$ with integer weight $w$. ($1 \le u, v \le N$, $u \ne v$, $1 \le w \le 1{,}000{,}000$)

The next line gives X Z. ($1 \le X, Z \le N$, $X \ne Z$)

The next line gives $P$. ($3 \le P \le \min(20, N - 3)$)

The next line gives $P$ distinct intermediate vertices $Y$ ($1 \le Y \le N$, $X \ne Y \ne Z$), separated by spaces.

Print the shortest distance from the start vertex $X$ to the destination vertex $Z$ that passes through all $P$ intermediate vertices. If the destination vertex $Z$ cannot be reached, print -1.