Regular checkup

The residents of DD Planet travel to a hospital for a regular checkup.

DD Planet has $N$ houses (numbered $1, 2, \dots, N$) and $M$ hospitals (numbered $N+1, N+2, \dots, N+M$). A deep river separates the area holding the houses from the area holding the hospitals. Crossing the river is possible only over a bridge. There are $B$ bridges (numbered $N+M+1, N+M+2, \dots, N+M+B$), and crossing any bridge takes $0$ seconds.

DD Planet also has $K$ roads that join houses, hospitals, and bridges. A road between two bridges is allowed. Because the deep river runs between the two areas, no road joins a house directly to a hospital.

Answer $Q$ questions.

• What is the minimum time for a resident of house $S_i$ to reach hospital $E_i$?

The first line contains the number of houses $N$ and the number of hospitals $M$ ($1 \le N, M \le 10\,000$), the number of bridges $B$ ($1 \le B \le 100$), the number of roads $K$ ($1 \le K \le 2 \times 10^4$), and the number of questions $Q$ ($1 \le Q \le 10^5$), separated by spaces.

Each of the next $K$ lines contains three integers $a$, $b$, and $K_i$, separated by spaces. A road joins point $a$ and point $b$, and travelling along that road takes $K_i$ ($1 \le K_i \le 10^9$) time.

Each of the next $Q$ lines contains $S_i$ and $E_i$ for one question, separated by spaces. ($1 \le S_i \le N$, $N+1 \le E_i \le N+M$)

On line $i$, print the answer to question $i$. If house $S_i$ cannot reach hospital $E_i$, print $-1$.