다람쥐

스웨덴 남부의 도시 룬드에는 보타니스카 트레드고르덴 공원이 있고, 이 공원에는 나무가 $n$그루 있다. 다람쥐들은 나무 $m$쌍 사이에 오솔길을 표시해 두었다.

가을이 오면 낙엽이 오솔길을 덮는다. 그러면 다람쥐들은 돌멩이로 모든 오솔길에 다시 표시해야 한다. 다람쥐들은 오솔길마다 다시 표시하는 데 드는 돌멩이 수를 알고 있다. $i$번째 오솔길은 $a_i$번 나무와 $b_i$번 나무를 잇고, 표시하는 데 $c_i$개의 돌멩이가 필요하다.

올해 다람쥐들은 오솔길을 전부 표시하지 않고 $n - 1$개만 표시하기로 했다. 표시한 오솔길은 모든 나무를 연결해야 한다. 즉 어떤 두 나무 사이에도 표시된 오솔길을 따라 이어지는 길이 있어야 한다. 또한 돌멩이의 총합이 가장 적도록 오솔길을 고른다.

계산을 마치기 전에 $q$마리의 다람쥐가 의견을 냈다. $i$번째 다람쥐는 오솔길 $x_i$를 표시하려면 $c_i$개가 아니라 $d_i$개의 돌멩이가 필요하다고 주장했다.

$i$번째 다람쥐의 주장만 참이고 나머지 다람쥐의 주장은 모두 거짓이라고 하자. 이때 새로운 계획에서 필요한 돌멩이의 총합은 얼마인가?

첫 줄에 자연수 $n$과 $m$이 주어진다($2 \le n \le 100\,000$, $1 \le m \le \min(200\,000, \frac{n \cdot (n-1)}{2})$). 각각 나무의 수와 나무 사이 오솔길의 수이다.

이어서 $m$개의 줄에 자연수 $a_i$, $b_i$, $c_i$가 주어진다($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 1\,000$). $i$번째 오솔길이 나무 $a_i$와 $b_i$를 잇고, 표시하는 데 $c_i$개의 돌멩이가 필요하다는 뜻이다.

다음 줄에는 정수 $q$가 주어진다($1 \le q \le 100\,000$). 확신하지 못하는 다람쥐의 수이다.

이어서 $q$개의 줄에 자연수 $x_i$와 $d_i$가 주어진다($1 \le x_i \le m$, $1 \le d_i \le 1\,000$). $i$번째 다람쥐 주장에 나오는 수이며, $x_i$는 입력에서 오솔길의 번호이다.

입력에서 모든 나무는 연결되어 있고, 두 나무 사이에 오솔길은 많아야 하나뿐이다.

$n$개의 줄을 출력한다. 첫 줄에는 다람쥐들의 주장을 고려하기 전에 필요한 돌멩이의 수를 출력한다. $i + 1$번째 줄에는 $i$번째 다람쥐의 주장만 참일 때 필요한 돌멩이의 수를 출력한다.

두 번째 예제에 대한 설명이다. 그림은 오솔길과 각 오솔길에 필요한 돌멩이의 수를 보여준다. 실선으로 그린 오솔길은 돌멩이로 표시하는 오솔길이고, 점선으로 그린 오솔길은 표시하지 않는 오솔길이다. $i$번째 다람쥐가 의심하는 오솔길은 빨간색으로 표시했다. 그림은 예제의 질의 순서대로 나열되어 있다.