정점이 개이고 간선이 개인 단순 무향 가중 연결 그래프가 주어진다.
두 정점 , 의 최단 거리를 구하는 쿼리를 번 처리하시오.
Input
첫 번째 줄에 정점의 개수 과 간선의 개수 이 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 각 줄에 간선이 잇는 두 정점 , 와 간선의 가중치 가 공백으로 구분되어 주어진다.
번째 줄에 쿼리의 개수 가 주어진다.
번째 줄부터 개의 줄에 걸쳐 각 줄에 최단 거리를 구해야 하는 두 정점 , 가 공백으로 구분되어 주어진다.
Output
첫 번째 줄부터 개의 줄에 걸쳐 각 줄에 정점 에서 정점 까지의 최단 거리를 출력한다.
Subtasks
Samples
예제 1
입력
4 3
1 2 3
4 1 1
3 1 2
2
1 3
4 2
출력
2
4
예제 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
출력
4
4
0
5