Cho một đồ thị vô hướng đơn, có trọng số và liên thông với $N$ đỉnh và $M$ cạnh.

Hãy xử lý $Q$ truy vấn, mỗi truy vấn yêu cầu tìm khoảng cách ngắn nhất giữa hai đỉnh $s$ và $e$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ cách nhau bởi dấu cách $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$.

Từ dòng thứ hai, $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$ và $w$ lần lượt là hai đỉnh được nối bởi cạnh và trọng số của cạnh đó $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$.

Dòng thứ $M+2$ chứa số lượng truy vấn $Q$ $(1 \le Q \le 10^{5})$.

Từ dòng thứ $M+3$, $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $s$ và $e$ là hai đỉnh cần tìm khoảng cách ngắn nhất $(1 \le s, e \le N)$.

Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng in ra khoảng cách ngắn nhất từ đỉnh $s$ đến đỉnh $e$ tương ứng với mỗi truy vấn.

Ví dụ

Dữ liệu vào 1

4 3
1 2 3
4 1 1
3 1 2
2
1 3
4 2

Dữ liệu ra 1

2
4

Dữ liệu vào 2

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

Dữ liệu ra 2

4
4
0
5