Khách sạn nơi các thí sinh tham dự kỳ thi Olympic truyền thống 30 tháng 4 đang lưu trú có ~N~ phòng được đánh số từ ~1~ đến ~N~, được nối với nhau bằng ~M~ hành lang hai chiều. Hành lang thứ ~i~ nối hai phòng ~U_i~ và ~V_i~, có độ dài ~L_i~. Hệ thống các hành lang ở khách sạn đảm bảo tính liên thông giữa các phòng, nghĩa là giữa hai phòng bất kỳ luôn tồn tại đường đi trực tiếp hoặc qua các phòng trung gian.

Sau khi hoàn thành các bài thi, có ~Q~ thí sinh được ban tổ chức kỳ thi mời tham gia một trò chơi. Ban tổ chức chuẩn bị còi cảnh báo ở ~K~ phòng được đánh số ~X_1, X_2, \dots, X_K~. Thí sinh thứ ~i~ sẽ được đưa đến phòng đánh số ~S_i~ và cần phải di chuyển đến phòng được đánh số ~T_i~ và các thí sinh cần tránh xa các phòng có còi cảnh báo nhất có thể.

Độ an toàn của một phòng được tính bằng khoảng cách ngắn nhất tính theo tổng độ dài các hành lang nối từ phòng đó đến 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ủa các phòng trên đường đi đó (kể cả phòng xuất phát và phòng đích đến). Mỗi thí sinh cần chọn đường đi có độ an toàn cao nhất để di chuyển đến đích. Những thí sinh chọn được một lộ trình tối ưu sẽ nhận được một phần quà từ ban tổ chức kỳ thi.

Yêu cầu: Hãy giúp ban tổ chức tính giá trị độ an toàn lớn nhất có thể đạt được cho mỗi thí sinh để có thể trao quà cho các thí sinh chọn được lộ trình tối ưu.

Input

• Dòng đầu chứa hai số nguyên ~N, M~ ~(1 \le N \le 10^5; 1 \le M \le 2 \cdot 10^5)~;

• Mỗi dòng trong số ~M~ dòng tiếp theo gồm ba 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)~;

• Dòng thứ ~i~ trong số ~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

In ra ~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.

Scoring

Sample Input 1

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

Sample Output 1

4
0

Notes

Sơ đồ của khách sạn có dạng như hình dưới. Độ an toàn của các phòng trong trường hợp này lần lượt là ~3, 0, 7, 7, 4~.

• Thí sinh đầu tiên có thể di chuyển theo lộ trình ~3 \rightarrow 4 \rightarrow 5~ có độ an toàn của các phòng lần lượt là ~7, 7, 4~ và độ an toàn thấp nhất là ~4~. Nếu thí sinh di chuyển theo lộ trình ~3 \rightarrow 1 \rightarrow 5~ thì độ an toàn thấp nhất sẽ là ~3~ và không phải lộ trình tối ưu.

• Thí sinh thứ hai có lộ trình di chuyển kết thúc ở một phòng có còi báo động nên độ an toàn thấp nhất là ~0~.