최단 경로들

Nikola는 Bit 마을에 살고 있고 Hex 마을에 사는 Anita의 남자친구이다. Nikola는 주변 지도를 아주 잘 알고 있어서 두 마을 사이의 최단 경로를 찾았다. 그리고 이 경로를 운 좋은 경로라고 부르기로 했다. 주변 지도는 서로 다른 마을을 잇는 양방향 도로의 집합으로 표현된다.

어떤 날, 이 나라의 대통령이 도로에 공사를 하기로 했다. 나라의 교통을 유지하기 위하여, 오직 하루에 하나의 도로만 닫기로 했다.

운 좋은 경로에 있는 도로에 대해서, Nikola는 그 도로가 닫혔을 때 Anita와의 최단 경로의 길이를 알고 싶어 한다.

입력의 첫째 줄은 4개의 정수로 이루어진다: n - 도시의 개수; m - 도로의 개수; a - Bit 마을(Nikola가 살고 있는 마을)의 번호; b - Hex 마을(Anita가 살고 있는 마을)의 번호.

마을들에는 1부터 n까지의 번호가 부여된다. 다음 m개의 줄은 u, v, w 3개의 정수를 포함하며 도로에 대한 정보를 준다: 마을 u와 마을 v는 길이 w의 도로로 이어져 있다.

입력의 마지막 줄은 숫자 k와 k개의 숫자(v1(=a), v2, …, vk(=b))로 이루어 지고, Nikola의 운 좋은 경로를 나타낸다.

각각의 정수 t = 1 … k – 1에 대해, 각 줄마다 도로 (vt, vt+1)가 닫혔을 경우에 마을 a와 마을 b 사이의 최단 경로의 길이를 출력하라. 만약 경로가 없다면 -1을 출력하라.

• 1 ≤ n ≤ 2000, 1 ≤ m ≤ 100.000
• 1 ≤ a, b ≤ n
• 1 ≤ w ≤ 100.000
• 서로 다른 두 도시 사이에는 최대 하나의 도로가 존재한다.
• 주어진 경로는 마을 a와 마을 b 사이의 최단 경로 중 하나이다.