시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB94463040.000%

문제

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

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

입력

첫 번째 줄에 정점의 개수 $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)$

출력

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

예제 입력 1

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

예제 출력 1

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

예제 출력 2

4
4
0
5