휴가 계획

에어 보비니아는 소가 사는 농장 $N$개를 항공편으로 잇는다. 농장에는 $1$번부터 $N$번까지 번호가 붙어 있고, 그중 $1$번부터 $K$번까지가 허브다.

지금 운항하는 단방향 항공편은 $M$개다. $i$번 항공편은 농장 $u_i$에서 농장 $v_i$로 가고, 요금은 $d_i$달러다.

에어 보비니아는 편도 여행 $Q$건을 접수했다. $i$번 여행은 농장 $a_i$에서 출발해 농장 $b_i$에서 끝난다. 여행 경로는 항공편을 원하는 대로 이어 붙여 만들고, 같은 농장을 여러 번 지나도 된다. 다만 경로에 허브가 적어도 하나 들어가야 한다. 출발 농장이나 도착 농장이 허브인 경우도 이 조건을 만족한다. 출발 농장과 도착 농장이 같으면 항공편을 한 번도 타지 않는 경로도 경로로 치며, 이때는 그 농장이 허브여야 조건을 만족한다.

이 조건 때문에 $a_i$에서 $b_i$로 가는 경로가 아예 없을 수 있다. 경로가 있는 여행마다 최소 요금을 구하라.

$1 \le N \le 200$, $1 \le K \le 100$, $K \le N$, $1 \le M \le 10\,000$, $1 \le d_i \le 1\,000\,000$, $1 \le Q \le 10\,000$이다. 같은 두 농장을 잇는 항공편이 여러 개 있을 수 있고, 출발 농장과 도착 농장이 같은 항공편도 있을 수 있다.

• 첫째 줄에 $N$, $M$, $K$, $Q$가 주어진다.
• 다음 $M$개 줄 중 $i$번째 줄에는 $i$번 항공편의 $u_i$, $v_i$, $d_i$가 주어진다.
• 다음 $Q$개 줄 중 $i$번째 줄에는 $i$번 여행의 $a_i$, $b_i$가 주어진다.

• 첫째 줄에 유효한 경로가 있는 여행의 개수를 출력한다.
• 둘째 줄에 그 여행들의 최소 요금을 모두 더한 값을 출력한다. 유효한 경로가 있는 여행이 하나도 없으면 $0$을 출력한다.

예제 입력에는 농장이 세 개 있고 $1$번 농장이 허브다. 농장 $3$에서 농장 $1$로 가는 $10$달러짜리 항공편이 있고, 나머지 항공편도 같은 방식으로 읽는다.

농장 $3$에서 농장 $2$로 가는 가장 싼 경로는 농장 $1$을 거치며 요금은 $10 + 7 = 17$이다. 농장 $2$에서 출발하는 항공편이 없으므로 농장 $2$에서 농장 $3$으로 가는 경로는 없다. 농장 $1$에서 농장 $2$로 가는 경로는 하나뿐이고 요금은 $7$이다.