Homing

Mr. Kim visits his hometown every year. He always drives along the shortest path to get there, and because he is very economical, he fills the tank with exactly the amount of gasoline needed for that shortest path. Last year an unexpected accident blocked a road on his shortest path, forced him onto a detour, and he ran out of gasoline before reaching home.

This year he wants to carry enough gasoline to survive one unexpected accident. Statistics say that at most one accident happens per day, and his hometown is always reachable within a single day of driving. So he wants to fill the tank with the smallest amount of gasoline that still lets him get home even if exactly one accident occurs somewhere on his shortest path. Whenever an accident happens, he recomputes the shortest remaining route from wherever he is standing.

The road network is a weighted graph $G = (V, E)$, where $V$ is the set of cities, $E$ is the set of roads, and the weight $w(e)$ of a road $e$ is the amount of gasoline needed to drive it. An accident always happens in the middle of a road, and Mr. Kim only learns about it when he arrives at one of the two cities that the road connects; accidents are never announced in advance.

Concretely, suppose an accident lies on a road of his shortest path, between the city he is about to leave and the next city on the path. At that moment he is standing at the earlier city, the gasoline used to get there is already spent, and he must reach home along the shortest route that does not use the blocked road.

For example, suppose the departure city is node 0 and the destination is node 5 in the figure below. The shortest path is $P = \langle 0, 1, 4, 5 \rangle$ with total weight $W(P) = 6$. If the accident blocks road $(0, 1)$, the shortest detour from node 0 that avoids it is $\langle 0, 2, 4, 5 \rangle$, which costs 2 more units than $P$. If it blocks road $(1, 4)$, the detour from node 1 is $\langle 1, 3, 5 \rangle$, costing 0 extra units. If it blocks road $(4, 5)$, the detour from node 4 is $\langle 4, 1, 3, 5 \rangle$, costing 4 extra units. The worst case needs 4 units on top of $W(P)$, so Mr. Kim must carry at least 10 units of gasoline.

Given the road network and the shortest path that Mr. Kim follows, find the smallest amount of gasoline he must carry so that he can always get home despite one accident.

The first line contains the number of test cases $T$ $(1 \le T \le 20)$.

Each test case begins with a line containing two integers $n$ and $m$ $(3 \le n, m \le 10000)$, the number of cities and the number of roads. Cities are numbered from $0$ to $n - 1$. Each of the next $m$ lines contains three integers $c$, $d$, and $w$, describing a two-way road between distinct cities $c$ and $d$ $(c \ne d)$ that needs $w$ units of gasoline to drive.

The next line describes Mr. Kim's shortest path. It starts with an integer $k$, the number of cities on the path, followed by those $k$ cities in order. The first is the departure city and the last is the destination.

For each test case, print a single line with the smallest amount of gasoline Mr. Kim must carry. If some accident could leave him with no way to reach home, print $-1$ for that test case instead.