황제의 도로

큐비코니아의 도로는 오랫동안 손보지 않아 상태가 나쁘다. 도로 하나는 서로 다른 두 도시 $A$와 $B$를 이으며 양방향으로 통행한다. 두 도시 사이를 잇는 도로는 많아야 하나이고, 지금 있는 도로만 써도 임의의 두 도시 사이를 오갈 수 있다. 새 황제는 세금을 또 올리면서 도로 일부를 보수하겠다고 약속했다. 보수를 마친 도로만으로 모든 도시 사이를 오갈 수 있어야 한다는 것이 약속의 내용이다.

공공사업부는 도로마다 보수 비용을 계산해 두었다. 이제 약속을 지키면서 보수 비용의 합이 가장 작아지는 도로 집합을 구해야 한다. 문제는 황제가 특정 도로 하나를 반드시 포함하라고 요구하면서도 그 도로를 아직 정하지 못했다는 점이다. 황제의 성이 있는 도시와 공주의 저택이 있는 도시를 잇는 도로일 수도 있고, 여름 궁전이 있는 도시와 바닷가 도시를 잇는 도로일 수도 있다. 결정이 늦어질 것을 걱정한 기술자들은 후보마다 답을 미리 알아 두려고 한다.

도로 목록과 보수 비용이 주어질 때 질의를 처리하는 프로그램을 작성하라. 각 질의는 반드시 보수해야 하는 도로 하나를 지정한다. 그 도로를 포함하면서, 보수를 마친 도로만으로 모든 도시 사이를 오갈 수 있게 하는 최소 보수 비용을 구하면 된다.

첫 줄에 도시 수 $N$과 도로 수 $R$이 주어진다 ($2 \le N \le 10^5$, $N - 1 \le R \le 2 \times 10^5$). 도시는 $1$부터 $N$까지 서로 다른 번호로 구분한다.

다음 $R$개 줄에는 도로 하나를 나타내는 세 정수 $A$, $B$, $C$가 주어진다 ($1 \le A < B \le N$, $1 \le C \le 10^4$). 도시 $A$와 도시 $B$를 잇는 도로가 있고 그 도로의 보수 비용이 $C$라는 뜻이다. 두 도시 사이를 잇는 도로는 많아야 하나이고, 주어진 도로만 써도 임의의 두 도시 사이를 오갈 수 있다.

다음 줄에 질의 수 $Q$가 주어진다 ($1 \le Q \le 10^5$). 다음 $Q$개 줄에는 질의 하나를 나타내는 두 정수 $U$와 $V$가 주어진다 ($1 \le U < V \le N$). 반드시 보수해야 하는 도로가 도시 $U$와 도시 $V$를 잇는 도로라는 뜻이며, 이 도로는 입력에 주어진 $R$개의 도로 가운데 하나다. 같은 질의가 두 번 주어지지 않는다.

$Q$개 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답, 즉 질의가 지정한 도로를 포함하면서 보수를 마친 도로만으로 모든 도시 사이를 오갈 수 있게 하는 최소 보수 비용을 정수로 출력한다.