Yêu cầu: Một khách sạn có \(N\) phòng và \(M\) hành lang hai chiều, hành lang thứ \(i\) nối giữa hai phòng \(U_i, V_i\) và có độ dài \(L_i\). Có \(K\) phòng được đặt còi cảnh báo. "Độ an toàn" của một phòng là khoảng cách ngắn nhất tính theo tổng độ dài các hành lang tới một phòng có báo động. "Độ an toàn" của một đường đi là giá trị nhỏ nhất của độ an toàn các phòng trên đường đi đó. Cho \(Q\) thí sinh, thí sinh thứ \(i\) cần đi từ phòng \(S_i\) đến \(T_i\), hãy tính độ an toàn lớn nhất có thể đạt được trên đường đi tối ưu cho mỗi thí sinh.

Input

Đọc từ file văn bản EXIT.INP:

• Dòng đầu chứa hai số nguyên \(N, M\) (\(1 \le N \le 10^5; 1 < M < 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo gồm 3 số nguyên \(U_i, V_i, L_i\) (\(1 \le U_i, V_i \le N; 1 \le L_i \le 10^6\)).
• Dòng tiếp theo chứa một số nguyên \(K\) (\(1 \le K \le N\)).
• Dòng tiếp theo chứa \(K\) số nguyên \(X_1, X_2, \dots, X_K\) (\(1 \le X_i \le N\)).
• Dòng tiếp theo chứa một số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo gồm hai số nguyên \(S_i, T_i\) (\(1 \le S_i, T_i \le N\)).

Output

Ghi ra file văn bản EXIT.OUT:

• Gồm \(Q\) dòng, mỗi dòng một số nguyên là độ an toàn lớn nhất có thể đạt được cho thí sinh tương ứng.

Example

6 6
1 2 5
2 3 2
3 4 2
4 5 2
5 6 5
2 5 3
2
1 6
3
3 4
2 5
1 3

7
5
0

Scoring

• Subtask \(1\) (\(1\) điểm): \(K \le 10; Q = 1; M = N - 1\) và mỗi phòng kết nối với không quá \(2\) hành lang.
• Subtask \(2\) (\(1\) điểm): \(K \le 10; Q = 1; M = N - 1\).
• Subtask \(3\) (\(1\) điểm): \(M = N - 1\) và mỗi phòng kết nối với không quá \(2\) hành lang.
• Subtask \(4\) (\(1\) điểm): \(M = N - 1\).
• Subtask \(5\) (\(1\) điểm): \(Q = 1\).
• Subtask \(6\) (\(1\) điểm): Không có ràng buộc nào thêm.