Trong thành phố Z có ~n~ trạm xe buýt, có ~m~ tuyến dường cho xe buýt chạy bắt đầu từ trạm ~a_i~ và kết thúc ở trạm ~b_i~, tốn khoảng thời gian ~t_i~.

Bình là một sinh viên mới vào thành phố, mỗi ngày Bình cần phải đi học bằng xe buýt từ trạm ~c_j~ đến trạm ~d_j~. Bình muốn sử dụng nhiều nhất là ~k~ tuyến cho hành trình của mình. Bình có ~q~ truy vấn: Đi từ trạm ~c_j~ đến trạm ~d_j~ chỉ sử dụng nhiều nhất là ~k~ tuyến thì thời gian ngắn nhất là bao nhiêu?

Yêu cầu

Hãy tìm thời gian ngắn nhất để đi từ trạm ~c_j~ đến trạm ~d_j~.

Dữ liệu đầu vào

Gồm ~2 + m + q~ dòng:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(2 \le n \le 70,\ 1 \le m \le 10^6)~ số trạm xe buýt và số tuyến đường.
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i~ và ~t_i~ tương ứng là đi từ trạm ~a_i~ đến trạm ~b_i~ tốn thời gian ~t_i~ ~(1 \le a_i, b_i \le n,\ 1 \le t_i \le 10^6)~.
• Dòng kế tiếp chứa hai số nguyên ~k~ và ~q~ ~(1 \le k \le 10^9,\ 1 \le q \le n^2)~, tương ứng với số tuyến đường nhiều nhất được sử dụng và số truy vấn.
• ~q~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~c_j~ và ~d_j~ ~(1 \le c_j, d_j \le n)~, tương ứng với truy vấn là đi từ trạm ~c_j~ và ~d_j~.

Dữ liệu đầu ra

Gồm ~q~ dòng tương ứng, dòng thứ ~j~ in ra dường đi ngắn nhất của truy vấn thứ ~j~ hoặc ~-1~ nếu không tìm thấy được đường đi.

Ràng buộc dữ liệu

• Có 20% số test ~k = 1~.
• Có 30% số test ~1 \le k \le n \le 7~.
• Có 50% số test không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
1 3
1 4
4 2
3 3

OUTPUT

10
-1
0

Giải thích: Đi từ ~1~ đến ~4~ tốn chi phí ~10~, từ ~4~ tới ~2~ không có đường đi, từ ~3~ đến ~3~ chi phí là ~0~.

Ví dụ 2

INPUT

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
2 3
1 4
4 2
3 3

OUTPUT

6
4
0