선심성 고속도로망

선거에서 이기는 일은 생각보다 쉬웠다. 예산을 무너뜨리지 않으면서 전국을 잇는 고속도로망을 제대로 깔겠다고 약속하는 것으로 충분했다. 행복은 오래가지 않았다. 시민들이 그 약속의 이행을 따지기 시작했다.

나라에는 대도시가 $n$개 있다. 교통부는 건설할 수 있는 고속도로 노선 $m$개와 각 노선의 건설 비용을 정리한 지도를 만들었다. 품질관리위원회는 비용이 $l$보다 싼 고속도로를 허가하지 않고, 예산규제위원회는 비용이 $h$보다 비싼 고속도로를 허가하지 않는다. 전국망이라고 내세우려면 두 제약 안에서 직접 또는 간접으로 연결되는 도시 쌍의 수를 최대로 만들어야 한다. 그런 도로망 가운데 비용이 가장 적은 것을 찾아야 하고, 빠르게 찾아야 한다. 두 제약을 지키면서 연결되는 도시 쌍의 수가 최대인 고속도로망 가운데 가장 저렴한 것의 비용을 구하라.

상황은 더 나쁘다. 두 위원회는 경쟁자의 영향을 받고 있어서, 힘들게 준비한 계획을 발표할 때마다 판정 $l$과 $h$를 바꿔 버린다. 그래서 매번 처음부터 다시 계산해야 한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

각 테스트 케이스의 첫 줄에 도시의 수 $n$과 건설 가능한 노선의 수 $m$이 주어진다. ($1 \le n \le 1\,000$, $0 \le m \le 100\,000$)

다음 $m$개의 줄에는 각각 세 정수 $x$, $y$, $w$가 주어진다. ($1 \le x, y \le n$, $x \ne y$, $1 \le w \le 1\,000\,000$) 도시 $x$와 도시 $y$를 비용 $w$로 잇는 양방향 고속도로를 건설할 수 있다는 뜻이다. 같은 도시 쌍을 잇는 노선이 여러 개 있을 수도 있다.

그다음 줄에 위원회 판정의 개수 $q$가 주어진다. ($1 \le q \le 1\,000\,000$) 이어지는 $q$개의 줄에는 각각 두 정수가 주어진다. 첫 줄에는 첫 번째 판정 $l_1$, $h_1$이 그대로 주어진다. 나머지 판정은 부호화되어 있다. $j > 1$인 $j$번째 줄의 두 수는 $l_j + c_{j-1}$과 $h_j + c_{j-1}$이고, $l_j$와 $h_j$가 실제 판정, $c_{j-1}$은 직전 판정 $l_{j-1}$, $h_{j-1}$에 대한 정답이다.

모든 판정은 $1 \le l_j \le h_j \le 1\,000\,000$을 만족한다.

각 테스트 케이스마다 판정 하나에 한 줄씩, 모두 $q$개의 줄을 출력한다. $j$번째 줄에는 위원회의 제약을 지키면서 연결되는 도시 쌍의 수를 최대로 만드는 고속도로망의 최소 건설 비용 $c_j$를 출력한다.

첫 번째 예제에서 실제 판정은 $(1, 2)$, $(1, 4)$, $(2, 3)$, $(3, 5)$, $(4, 5)$이다. 각 판정에 대해 가장 저렴한 고속도로망은 순서대로 $\{(1, 2), (4, 5)\}$, $\{(2, 1), (1, 5), (5, 4), (4, 3)\}$, $\{(1, 2), (1, 5), (3, 4)\}$, $\{(1, 5), (5, 2), (2, 3), (3, 4)\}$, $\{(3, 2), (2, 5), (1, 4)\}$이다.