26262번 - 트리 더하기 1

$N$개의 정점과 $N$개의 양방향 간선으로 이루어진 연결 그래프 $G$가 주어진다. 정점에는 $1$부터 $N$까지의 번호가 매겨져 있다. $i$번째 간선은 정점 $u_i$와 정점 $v_i$를 양방향으로 연결하고 간선의 길이는 $d_i$이다.

정점의 순서쌍 $\left( x_i,y_i \right)$가 $Q$개 주어진다. 각각의 순서쌍에 대해 정점 $x_i$와 정점 $y_i$를 잇는 최단 경로의 길이를 구하시오.

첫 번째 줄에 정점의 개수 $N$이 주어진다. $(2\leq N\leq 2\times 10^5)$

두 번째 줄부터 $N$개의 줄에 걸쳐 간선의 정보 $u_i,v_i,d_i$가 공백으로 구분되어 주어진다. $(1\leq u_i\lt v_i\leq N;$ $1\leq d_i\leq 10^9)$ $i\neq j$이고 $\left( u_i,v_i \right) =\left( u_j,v_j \right)$인 중복 간선이 입력으로 주어질 수 있다.

$N+2$ 번째 줄에 정수 $Q$가 주어진다. $(1\leq Q\leq 2\times 10^5)$

$N+3$ 번째 줄부터 $Q$개의 줄에 걸쳐 정점 $x_i$와 정점 $y_i$가 공백으로 구분되어 주어진다. $(1\leq x_i\lt y_i\leq N)$

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄부터 $Q$개의 줄에 걸쳐 $x_i$와 $y_i$를 잇는 최단 경로의 길이를 출력한다.