관광 명소

바이트아사르(Byteasar)는 비팅엄(Bitingham)에서 출발해 바이트버그(Byteburg)까지 여행하려 한다. 가는 길에 그는 꼭 들르고 싶은 명소들, 즉 흥미로운 기념물과 훌륭한 식당, 그리고 여러 관광지를 방문하고 싶어 한다. 방문 순서가 완전히 자유롭지는 않다. 예를 들어 바이트아사르는 디지테스트(Digitest)에서 푸짐한 저녁을 먹은 직후에 비트포크 성(Bitfork Castle)의 뾰족한 탑에 오르고 싶지는 않으며, 마찬가지로 유명한 콤프레소(Compresso) 커피를 마시러 집 시티(Zip City, 어떤 이들은 십 시티라고 부른다)에 들르는 것도 저녁 식사 전보다는 후에 하고 싶어 한다. 다행히 그의 일정에는 어느 정도 여유가 있어 몇 가지 순서 중에서 고를 수 있다. 다만 살인적인 기름값 때문에 그는 절약을 위해 되도록 가장 짧은 경로를 따라가고 싶어 한다. 그의 요구 조건을 만족하는 가장 짧은 경로의 길이를 구하도록 도와주자.

도로망은 $n$개의 지점과 이들을 잇는 $m$개의 도로로 이루어져 있다. 지점에는 $1$부터 $n$까지, 도로에는 $1$부터 $m$까지 번호가 매겨져 있다. 각 도로는 서로 다른 두 지점을 잇는 양방향 도로이며, 저마다 길이가 있다. 서로 다른 도로는 오직 지점(도로의 양 끝점)에서만 만나고, 지점 바깥에서는 교차하지 않는다(입체 교차로와 터널 덕분이다). 한 쌍의 지점은 최대 하나의 도로로만 직접 연결되지만, 두 지점 사이에 도로 두 개 이상으로 이루어진 경로는 여러 개 있을 수 있다.

바이트아사르가 방문하려는 지점의 수를 $k$라 하자. 비팅엄은 번호 $1$, 바이트버그는 번호 $n$이며, 바이트아사르가 방문하려는 지점들은 번호 $2, 3, \dots, k+1$을 가진다.

위 그림은 도로망의 한 예이다. 바이트아사르가 지점 $2, 3, 4, 5$를 방문하려 하고, $2$를 $3$보다 먼저, $4$와 $5$를 $3$보다 나중에 방문하고 싶어 한다고 하자. 그러면 가장 짧은 경로는 지점 $1, 2, 4, 3, 4, 5, 8$을 지나며 그 길이는 $19$이다.

지점 $4$가 경로에서 지점 $3$의 앞과 뒤에 모두 나타난다는 점에 주목하라. 이는 전혀 문제가 되지 않으며, 바이트아사르가 지점 $3$을 방문하기 전에는 지점 $4$에 멈추지 않는다는 뜻이다. 그의 요구 조건이 그것을 허용하지 않기 때문이다. 다만 지점 $3$을 방문하기 전에 지점 $4$를 멈추지 않고 그냥 지나가는 것은 허용되며, 실제로 그는 그렇게 할 것이다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 도로망의 정보, 바이트아사르가 방문하기로 한 지점들의 목록, 그리고 그가 지점들을 방문하려는 순서에 대한 제약을 읽는다.
• 선택된 모든 지점을 올바른 순서로 지나는 가장 짧은 경로의 길이를 구한다.
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 세 정수 $n$, $m$, $k$가 공백 하나로 구분되어 주어진다. $2 \le n \le 20{,}000$, $1 \le m \le 200{,}000$, $0 \le k \le 20$이며, 추가로 $k \le n - 2$가 성립한다.

이어지는 $m$개의 줄에는 도로의 정보가 한 줄에 하나씩 주어진다. $(i+1)$번째 줄에는 세 정수 $p_i$, $q_i$, $l_i$가 공백 하나로 구분되어 주어지며, $1 \le p_i < q_i \le n$, $1 \le l_i \le 1{,}000$이다. 이 수들은 지점 $p_i$와 $q_i$를 잇는 길이 $l_i$의 도로를 나타낸다. 각 입력 데이터에서 비팅엄에서 바이트버그로, 그리고 바이트아사르가 방문하려는 각 지점으로 이동하는 것이 항상 가능하다고 가정해도 된다.

$(m+1)$번째 줄에는 정수 $g$가 하나 주어진다($0 \le g \le k \cdot (k-1) / 2$). 이는 바이트아사르가 지점들을 방문하려는 순서에 대한 제약의 수이다. 이 제약들은 이어지는 $g$개의 줄에 한 줄에 하나씩 주어진다. $(m+i+1)$번째 줄에는 두 정수 $r_i$와 $s_i$가 공백 하나로 구분되어 주어지며, $2 \le r_i \le k+1$, $2 \le s_i \le k+1$, $r_i \ne s_i$이다. 쌍 $(r_i, s_i)$는 바이트아사르가 지점 $s_i$를 방문하기 전에 지점 $r_i$를 방문하고 싶어 한다는 뜻이다. 다만 이는 그가 $r_i$를 방문하기 전에 $s_i$를 멈추지 않고 지나가거나, $s_i$를 방문한 뒤에 $r_i$를 멈추지 않고 지나가는 것을 막지는 않는다. 관광지에 멈춰 방문하지만 않는다면 그렇게 해도 된다. 각 입력 데이터에 대해 모든 제약을 만족하는 방문 순서가 적어도 하나 존재함이 보장된다.

첫째 줄에 정수 하나를 출력한다. 이는 바이트아사르가 선택한 모든 지점을 올바른 순서로 지나는, 비팅엄에서 바이트버그까지의 가장 짧은 경로의 길이이다.