1883번 - 1&&3

세훈이와 찬우는 수많은 그래프 문제를 풀며 좋은 그래프 문제에 대한 소신을 가지게 되었다.

• 세훈이는 특별한 예외 처리가 필요하지 않도록 $1$반적(일반적)인 그래프가 주어져야 한다고 생각한다. 세훈이가 생각하는 일반적인 그래프는 무방향 단순 연결 그래프이다. 즉, 중복되는 간선이 없고 모든 정점이 연결되어 있으며, 서로 다른 두 정점을 잇는 간선만 존재하는 무방향 그래프가 주어져야 한다.
• 찬우는 차수가 큰 정점이 많을수록 그래프가 난잡해진다고 생각한다. 구체적으로, 차수가 $3$ 이상인 정점의 개수가 $3$개 미만이어야 한다.

세훈이와 찬우는 $1$반적이면서 차수가 $3$ 이상인 정점이 $3$개 미만인 그래프에 1 && 3 그래프라는 이름을 붙였다. 그래프를 정의하였으니 정점 사이의 최단 거리를 찾는 것은 여러분의 몫이다. 정점이 $V$개, 간선이 $E$개인 1 && 3 그래프가 주어질 때, 임의의 두 정점 사이의 최단 거리를 계산하는 쿼리를 $Q$번 처리하는 프로그램을 작성해 보자.

첫째 줄에 정점의 개수 $V$, 간선의 개수 $E$, 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. $(2 \le V \le 500\,000;$ $V-1 \le E \le 500\,000;$ $1 \le Q \le 200\,000)$

둘째 줄부터 $E$개의 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $x$, $y$와 간선의 가중치 $c$가 공백으로 구분되어 주어진다. $(1 \le x,y \le V;$ $1 \le c \le 10^9;$ $x \neq y)$

그 다음 줄부터 $Q$개의 줄에 걸쳐 $a$, $b$가 공백으로 구분되어 주어진다. 이는 $a$번 정점과 $b$번 정점 사이의 최단 거리를 계산하는 쿼리를 의미한다. $(1 \le a, b \le V)$

입력으로 주어지는 모든 수는 정수이며, 주어지는 그래프는 1 && 3 그래프이다.

$Q$개의 줄에 걸쳐 쿼리의 결과를 입력받은 순서대로 한 줄에 하나씩 출력한다.