정점이 $N$개이고 간선이 $M$개인 단순 무향 가중 연결 그래프가 주어진다.

두 정점 $s$, $e$의 최단 거리를 구하는 쿼리를 $Q$번 처리하시오.

Input

첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

두 번째 줄부터 $M$개의 줄에 걸쳐 각 줄에 간선이 잇는 두 정점 $u$, $v$와 간선의 가중치 $w$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

$M+2$번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \le Q \le 10^{5})$

$M+3$번째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 최단 거리를 구해야 하는 두 정점 $s$, $e$가 공백으로 구분되어 주어진다. $(1 \le s, e \le N)$

Output

첫 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 정점 $s$에서 정점 $e$까지의 최단 거리를 출력한다.

Examples

Input 1

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

Output 1

2
4

Input 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

Output 2

4
4
0
5