Công ty du lịch \(X\) tổ chức các hành trình du lịch trong vùng lãnh thổ gồm \(N\) địa điểm du lịch trọng điểm được đánh số từ \(1\) tới \(N\), từ một địa điểm du lịch bất kì luôn tồn tại đường đi đến các địa điểm còn lại. Hệ thống giao thông trong vùng gồm \(M\) tuyến đường hai chiều, tuyến đường thứ \(i\) (\(i = 1, 2, 3, ... , M\)) cho phép đi từ địa điểm \(u_i\) đến địa điểm \(v_i\) với chi phí đi lại là \(d_i\).

Vấn đề đặt ra, khi có yêu cầu từ khách hàng muốn đi từ địa điểm du lịch \(u_i\) đến \(v_i\) thì công ty phải tìm được một hành trình với tổng chi phí (được tính như là tổng chi phí của các tuyến đường mà hành trình đi qua) nhỏ nhất.

Yêu cầu: Cho \(Q\) yêu cầu từ khách hàng, em hãy viết chương trình với mỗi yêu cầu tìm đường đi ngắn nhất giữa hai địa điểm \(u_i\) và \(v_i\).

Input

• Dòng đầu chứa \(2\) số \(N\) và \(M\) tương ứng là số địa điểm và số tuyến đường \((1 \leq N, M \leq 10^5, M \geq N − 1, M − N \leq 20)\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(3\) số nguyên \(u_i, v_i, d_i\) \((1 \leq u_i, v_i \leq N, 1 \leq d_i \leq 10^9, u_i \neq v_i)\).
• Dòng tiếp theo chứa số nguyên \(Q\) \((1 \leq Q \leq 10^5)\) là số yêu cầu của khách hàng.
• \(Q\) dòng tiếp theo, mỗi dòng là một yêu cầu gồm \(2\) số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i, v_i \leq n)\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) tương ứng là kết quả yêu cầu thứ \(i\) trong tệp dữ liệu vào đường đi ngắn nhất giữa \(u_i\) và \(v_i\).

Scoring

• Subtask \(1\) (\(28.5\%\) số điểm): \(N \leq 5000\)
• Subtask \(2\) (\(28.5\%\) số điểm): \(M = N - 1\)
• Subtask \(3\) (\(43\%\) số điểm): Không có giới hạn gì thêm

Example

3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3

3
4
1