Shortest Paths

Nikola lives in the town of Bit and is dating Anita, who lives in the town of Hex. Nikola knows the surrounding map so well that he has found one shortest route between the two towns, which he calls the lucky route. The map is given as a set of bidirectional roads connecting distinct towns.

One day the president decides to carry out roadworks. To keep the country's traffic flowing, exactly one road is closed each day.

For each road on the lucky route, Nikola wants to know the length of the shortest route from his town to Anita's town when that road is closed.

The first line contains four integers $n$, $m$, $a$, $b$: $n$ is the number of towns, $m$ is the number of roads, $a$ is the number of the town of Bit (where Nikola lives), and $b$ is the number of the town of Hex (where Anita lives).

The towns are numbered from $1$ to $n$. Each of the next $m$ lines contains three integers $u$, $v$, $w$, meaning that town $u$ and town $v$ are connected by a road of length $w$.

The last line contains an integer $k$ followed by $k$ town numbers $v_1, v_2, \ldots, v_k$ (with $v_1 = a$ and $v_k = b$), describing Nikola's lucky route.

For each $t = 1, 2, \ldots, k-1$, print on its own line the length of the shortest route from town $a$ to town $b$ when road $(v_t, v_{t+1})$ is closed. If no such route exists, print $-1$.

• $1 \le n \le 2000$, $1 \le m \le 100000$
• $1 \le a, b \le n$
• $1 \le w \le 100000$
• There is at most one road between any two distinct towns.
• The given lucky route is one of the shortest routes from town $a$ to town $b$.