Tỉnh Ninh Bình là một trong các tỉnh phát triển mạnh về du lịch. Tại đây, có một số món quà lưu niệm rất được khách du lịch ưa thích là các sản phẩm thủ công mĩ nghệ chế tác từ lá của cây bồ đề.

Bản đồ giao thông của tỉnh có thể mô tả là một đồ thị có N đỉnh và M con đường hai chiều, mỗi con đường nối trực tiếp hai đỉnh nào đó, để di chuyển trên từng con đường này sẽ mất chi phí w_i tương ứng, không có con đường nào nối một đỉnh với chính nó.

Có K đỉnh mà tại đó có bán món quà lưu niệm làm từ lá cây bồ đề, tại đỉnh K_i món quà sẽ được bán với giá C_i.

Có P vị khách muốn thực hiện hành trình của mình, vị khách P_i muốn di chuyển từ đỉnh u_i đến đỉnh v_i và đều muốn mua được món quà lưu niệm từ một trong các đỉnh

có bán quà mà trên hành trình sẽ đi qua.

Yêu cầu: Hãy tính chi phí bé nhất để mỗi vị khách di chuyển theo hành trình của mình và mua được một món quà lưu niệm.

Dữ liệu vào:

+ Dòng đầu gồm bốn số nguyên dương N, M, K, P lần lượt là số đỉnh, số cạnh, số đỉnh có bán quà lưu niệm và số vị khách du lịch \((\ 1 \leq K \leq 100,\ 1 \leq P \leq 2.500,\ 2P \leq N \leq 10^{4},\ N - 1 \leq M\ \leq 10^{5})\).

+ M dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương u_i, v_i, w_i lần lượt là hai đỉnh của cạnh thứ i và chi phí di chuyển trên cạnh đó.

+ K dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương là số thứ tự của đỉnh có bán quà và giá bán tại đỉnh đó.

+ P dòng tiếp theo, dòng thứ i chứa 2 số nguyên dương u_i, v_i là điểm đầu và điểm cuối của hành trình vị khách thứ i muốn đi.

Kết quả:

+ Gồm P dòng, dòng thứ i ghi ra tổng chi phí di chuyển và mua quà lưu niệm nhỏ nhất của vị khách thứ i. Nếu không có đường đi cho hành trình của vị khách thứ i thì ghi ra số -1.

Ví dụ:

Ràng buộc:

+ 40% số điểm tương ứng với 40% test ứng với K = 1.

+ 40% số điểm tương ứng với 40% test ứng với P = 1.

+ 20% số điểm không có ràng buộc gì thêm.