정기검진

디디플래닛 주민은 정기검진을 받으러 병원에 간다.

디디플래닛에는 집이 $N$개($1, 2, \dots, N$번), 병원이 $M$개($N+1, N+2, \dots, N+M$번) 있다. 집이 모여 있는 구역과 병원이 모여 있는 구역은 깊은 강으로 갈라져 있다. 강을 건너려면 반드시 다리를 지나야 한다. 다리는 $B$개($N+M+1, N+M+2, \dots, N+M+B$번)이고, 어느 다리든 건너는 데 걸리는 시간은 $0$초라고 가정한다.

디디플래닛에는 집, 병원, 다리를 잇는 도로가 $K$개 있다. 다리와 다리를 잇는 도로도 있을 수 있다. 다만 집이 있는 구역과 병원이 있는 구역 사이에는 깊은 강이 흐르므로, 집과 병원을 직접 잇는 도로는 없다.

질문 $Q$개에 답해야 한다.

• $S_i$번 집에 사는 주민이 $E_i$번 병원까지 가는 데 걸리는 최소 시간은 얼마인가?

첫째 줄에 집의 수 $N$과 병원의 수 $M$ ($1 \le N, M \le 10\,000$), 다리의 수 $B$ ($1 \le B \le 100$), 도로의 수 $K$ ($1 \le K \le 2 \times 10^4$), 질문의 수 $Q$ ($1 \le Q \le 10^5$)가 공백으로 구분되어 주어진다.

둘째 줄부터 $K$개 줄에 정수 $a$, $b$, $K_i$가 공백으로 구분되어 주어진다. 지점 $a$와 지점 $b$를 잇는 도로가 있고, 그 도로를 지나는 데 $K_i$ ($1 \le K_i \le 10^9$)의 시간이 든다는 뜻이다.

그다음 $Q$개 줄에 질문의 $S_i$와 $E_i$가 공백으로 구분되어 주어진다. ($1 \le S_i \le N$, $N+1 \le E_i \le N+M$)

$i$번째 줄에 $i$번째 질문의 답을 출력한다. $S_i$번 집에서 $E_i$번 병원으로 갈 수 없으면 $-1$을 출력한다.