첫 번째 줄에 여행지의 수 N(5 <= N <= 200), 경로의 수 M(N – 1 <= M <= N * (N – 1) / 2), 기념품 가게가 있는 여행지의 수 L(1 <= L <= N), 여행자의 수 K(1 <= K <= 10,000)가 공백으로 구분하여 입력된다.

두 번째 줄에는 기념품 가게가 있는 여행지의 번호 L개가 공백으로 구분되어 차례대로 입력된다.

세 번째 줄부터 M개의 줄에는 각각 세 개의 정수 Xi, Yi, Vi가 입력된다. Xi에서 Yi로 이동하는데 드는 비용이 Vi임을 나타낸다. (단방향으로 Yi에서 Xi로 이동하는 것은 안된다.)

다음 줄부터 K개의 줄에는 두 개의 정수 Si, Ei가 입력된다. 각 여행자의 현재 위치와 목적지를 나타낸다.

#4742 upload 6 done 3 how_to_reg 2

마지막 여행지1 timer 1s memory 256MB

#4742

마지막 여행지1 1s 256MB