Di chuyển

Trong thành phố Z có \(n\) trạm xe buýt, có \(m\) tuyến đườ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 \(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\).

Input

Dữ liệu vào gồm:

• 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\)) là số trạm xe buýt và số tuyến đường.

• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(a_i, b_i, 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 đi từ trạm \(c_j\) đến trạm \(d_j\).

Ràng buộc:

• Có \(20\%\) số test \(k = 1\).

• Có \(30\%\) số test \(1 \le k < n \le 7\).

• Có \(50\%\) số test không ràng buộc gì thêm.

Output

In ra \(q\) dòng, dòng thứ \(j\) in ra thời gian đ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.

Example 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

Example 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

Note

Trong ví dụ 1: đi từ trạm \(1\) đến trạm \(4\) tốn thời gian \(10\), từ trạm \(4\) tới trạm \(2\) không có đường đi, từ trạm \(3\) đến trạm \(3\) chi phí là \(0\).