Hà Giang đang đi du lịch đất nước XYZ. Đất nước này gồm có \(n\) thành phố. Hà Giang muốn đi thăm thú giữa một số cặp thành phố của XYZ bằng xe bus và tìm hiểu được rằng có tổng cộng \(m\) tuyến bus trong đất nước này, tuyến bus thứ \(i\) xuất phát ở thành phố \(a_i\) và cập bến ở thành phố \(b_i\) trong \(t_i\) phút. Giang không phải là người kiên nhẫn nên cô ấy không muốn trung chuyển qua quá nhiều tuyến bus khác nhau để đến đích. Cụ thể, Giang nhờ bạn lập trình trả lời giúp cô ấy \(q\) câu hỏi, mỗi câu có dạng "Tính toán thời gian nhỏ nhất để di chuyển từ thành phố \(c_j\) đến thành phố \(d_j\) mà không phải leo lên quá \(k\) xe bus khác nhau?"

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(m\) (\(2\leq n\leq 70\), \(1\leq m\leq 10^6\)) lần lượt là số lượng thành phố và số lượng tuyến bus khác nhau.

Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa ba số nguyên dương \(a_i\), \(b_i\) và \(t_i\) (\(1\leq a_i, b_i\leq n\), \(1\leq t_i\leq 10^6\)).

Dòng tiếp theo chứa hai số nguyên dương \(k\) và \(q\) (\(1\leq k\leq 10^9\), \(1\leq q\leq n^2\)) lần lượt là số tuyến bus tối đa mà Giang muốn leo lên và số lượng câu hỏi mà cô ấy nhờ bạn trả lời giúp.

Dòng thứ \(i\) trong \(q\) dòng tiếp theo chứa hai số nguyên dương \(c_j\) và \(d_j\) \((1\leq c_j, d_j\leq n)\), thể hiện số hiệu thành phố khởi đầu và kết thúc trong câu hỏi thứ \(j\).

Output

In ra \(q\) dòng là câu trả lời cho từng câu hỏi tương ứng. Nếu không tồn tại lộ trình di chuyển bằng bus cho một cặp thành phố nào thì in ra \(-1\).

Ví dụ

Sample input 1

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

Sample output 1

10
-1
0

Minh họa cho câu hỏi đầu tiên

Sample input 2

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

Sample output 2

6
4
0

Minh họa cho câu hỏi đầu tiên

Sample input 3

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

Sample output 3

3
4
0

Minh họa cho câu hỏi đầu tiên

Ràng buộc:

• Subtask 1: \(k \leq n \leq 7\).
• Subtask 2: \(k \leq 3\).
• Subtask 3: \(k \leq n\).
• Subtask 3: Không có ràng buộc gì thêm.