귀향

김씨는 해마다 고향을 방문한다. 그는 언제나 고향까지 가는 최단 경로를 따라 운전하며, 매우 알뜰한 사람이라 그 최단 경로를 달리는 데 꼭 필요한 만큼만 연료를 채운다. 작년에는 최단 경로 위의 한 도로에서 예상치 못한 사고가 나 길이 막혔고, 어쩔 수 없이 우회하다가 집에 도착하기도 전에 연료가 바닥나 큰 곤란을 겪었다.

올해는 예상치 못한 사고가 한 번 나더라도 무사히 집에 도착할 수 있도록 넉넉히 연료를 준비하려고 한다. 통계에 따르면 사고는 하루에 많아야 한 번 일어나며, 하루 종일 운전하면 고향에는 반드시 도착할 수 있다. 그래서 그는 최단 경로 위 어디에선가 사고가 정확히 한 번 일어나더라도 집에 도착할 수 있는 가장 적은 양의 연료를 채우고자 한다. 사고가 나면 그는 서 있는 위치에서 남은 최단 경로를 다시 계산해 이동한다.

도로망은 가중치 그래프 $G = (V, E)$로 나타낸다. $V$는 도시들의 집합, $E$는 도시를 잇는 도로들의 집합이며, 각 도로 $e$의 가중치 $w(e)$는 그 도로를 달리는 데 필요한 연료의 양이다. 사고는 항상 도로 한가운데에서 일어나고, 김씨는 그 도로가 잇는 두 도시 중 하나에 도착해야 비로소 사고를 알 수 있다. 즉 사고는 미리 예고되지 않는다.

구체적으로, 사고가 최단 경로 위의 어떤 도로, 곧 그가 막 떠나려는 도시와 경로상 다음 도시를 잇는 도로에서 일어났다고 하자. 그 순간 그는 앞쪽 도시에 서 있고, 거기까지 오는 데 쓴 연료는 이미 소비했으며, 막힌 도로를 쓰지 않는 최단 경로로 집까지 가야 한다.

예를 들어 아래 그림에서 출발 도시가 0번, 도착 도시가 5번이라고 하자. 최단 경로는 $P = \langle 0, 1, 4, 5 \rangle$이고 그 총 가중치는 $W(P) = 6$이다. 사고가 도로 $(0, 1)$을 막으면 0번에서 그 도로를 피하는 최단 우회로는 $\langle 0, 2, 4, 5 \rangle$이고, 이는 $P$보다 2만큼 더 든다. 도로 $(1, 4)$가 막히면 1번에서의 우회로는 $\langle 1, 3, 5 \rangle$이고 추가 비용은 0이다. 도로 $(4, 5)$가 막히면 4번에서의 우회로는 $\langle 4, 1, 3, 5 \rangle$이고 추가 비용은 4이다. 가장 나쁜 경우 $W(P)$보다 4만큼 더 필요하므로, 김씨는 적어도 10만큼의 연료를 준비해야 한다.

도로망과 김씨가 따라가는 최단 경로가 주어질 때, 사고가 한 번 나더라도 언제나 집에 도착할 수 있도록 그가 준비해야 하는 가장 적은 연료의 양을 구하라.

첫째 줄에 테스트 케이스의 수 $T$ $(1 \le T \le 20)$가 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 수 $n$과 도로의 수 $m$ $(3 \le n, m \le 10000)$이 주어진다. 도시는 $0$번부터 $n - 1$번까지 번호가 매겨진다. 이어지는 $m$개의 줄에는 각각 세 정수 $c$, $d$, $w$가 주어지며, 이는 서로 다른 두 도시 $c$와 $d$ $(c \ne d)$를 잇고 달리는 데 연료 $w$만큼이 드는 양방향 도로를 뜻한다.

그다음 줄에는 김씨가 택한 최단 경로가 주어진다. 먼저 경로에 포함된 도시의 수 $k$가 주어지고, 이어서 그 $k$개의 도시가 지나는 순서대로 주어진다. 첫 번째 도시는 출발 도시, 마지막 도시는 도착 도시이다.

각 테스트 케이스마다 김씨가 준비해야 하는 가장 적은 연료의 양을 한 줄에 출력한다. 만약 어떤 사고로 인해 집에 도착할 방법이 아예 없어지는 경우가 있다면, 그 테스트 케이스에 대해서는 대신 $-1$을 출력한다.