Lập Kế Hoạch Du Lịch

Có $N$ trang trại và $K$ trạm trung chuyển (hub). Trạm trung chuyển là một tập con $K$ trang trại đầu tiên (trang trại $1$ đến $K$). Có $M$ chuyến bay một chiều giữa các trang trại, mỗi chuyến bay từ trang trại $u$ đến trang trại $v$ với chi phí $d$.

Cho $Q$ yêu cầu di chuyển, mỗi yêu cầu từ trang trại $a$ đến trang trại $b$. Một hành trình hợp lệ phải đi qua ít nhất một trạm trung chuyển (tức là tồn tại một trạm $h$ ($1\le h\le K$) sao cho có đường đi từ $a$ đến $h$ và từ $h$ đến $b$).

Với mỗi yêu cầu, tìm chi phí nhỏ nhất để đi từ $a$ đến $b$ qua ít nhất một trạm trung chuyển. Nếu không có hành trình hợp lệ nào, bỏ qua yêu cầu đó.

Dữ liệu vào

• Dòng 1: Bốn số nguyên $N$, $M$, $K$, $Q$.
• $M$ dòng tiếp theo: Mỗi dòng gồm ba số nguyên $u_i$, $v_i$, $d_i$ — chuyến bay từ trang trại $u_i$ đến $v_i$ với chi phí $d_i$.
• $Q$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $a_i$, $b_i$ — yêu cầu di chuyển từ $a_i$ đến $b_i$.

Dữ liệu ra

• Dòng 1: Số lượng yêu cầu có hành trình hợp lệ.
• Dòng 2: Tổng chi phí nhỏ nhất của tất cả các yêu cầu hợp lệ.

Ràng buộc

• $1\le N\le 200$
• $1\le K\le 100$, $K\le N$
• $1\le M\le 10000$
• $1\le d_i\le 1000000$
• $1\le Q\le 10000$

Ví dụ

Ghi chú

Cần xét mọi trạm trung chuyển có thể để tìm chi phí tối thiểu. Chi phí từ $a$ đến $b$ qua hub $h$ là $\text{dist}(a,h)+\text{dist}(h,b)$.