교통량 분석

BOJ 나라에는 $1$번부터 $N$번까지의 번호가 붙어 있는 $N$ 개의 도시가 있다. 또한, 서로 다른 두 도시를 잇는 $1$번부터 $N-1$번까지의 번호가 붙어 있는 $N-1$ 개의 도로가 존재한다. 임의의 서로 다른 두 도시는 도로들을 통해 이동할 수 있다. 다시 말해, BOJ 나라의 교통망은 트리 구조이다.

현대 오토에버에 새롭게 입사하게 된 선재는 BOJ 나라 도시의 유동 차량 수와 도로의 교통량을 분석해 최적화된 교통정보를 제공하는 과제를 맡게 되었다. 분석 결과에 따르면, 각 도시의 유동 차량 수와 교통량은 음이 아닌 정수로 표현할 수 있다. 또한, 각 도로의 교통량은 적어도 도로가 잇는 두 도시의 유동 차량 수의 합보다 같거나 크다.

현재, $i$번 도로의 교통량은 $A\_i$이다. 선재는 모든 도시의 유동 차량 수 합의 최댓값을 계산해 사용자들에게 제공하고자 한다. 그러나, 차세대 GIS를 개발하는 현대 오토에버는 교통량이 변화하면 이에 따라 실시간으로 이 값을 다시 계산하기로 결정했다!

물론 영리한 선재는 문제를 해결할 능력이 충분하지만, 현대 오토에버의 입사 동기인 당신에게 도움을 요청하고자 한다. 선재와 같이 과제를 해결해 보자.

첫 번째 줄에 도시의 수 $N$과 교통량이 변화한 횟수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N-1$ 개의 줄 중 $i$ 번째 줄에는 $i$번 도로가 잇는 두 도시의 번호 $x\_i$, $y\_i$와 현재 $i$번 도로의 교통량 $A\_i$가 공백으로 구분되어 주어진다.

$N+1$ 번째 줄부터 $Q$ 개의 줄 중 $i$ 번째 줄에는 교통량이 변화한 도로의 번호 $k\_i$와, 변화한 교통량 $v\_i$가 공백으로 구분되어 주어진다. 이는 $k\_i$번 도로의 교통량이 $v\_i$로 변화했다는 것을 의미한다.

첫 줄에는 현재 교통량을 토대로 구할 수 있는 BOJ 나라의 총 유동 차량 수로 가능한 최댓값을 출력한다.

다음 $Q$ 개의 줄의 각 줄에는, 교통량이 변화할 때 마다 변화한 교통량을 토대로 구할 수 있는 BOJ 나라의 총 유동 차량 수로 가능한 최댓값을 출력한다.

• $2 \leq N \leq 100\\,000$
• $1 \leq Q \leq 100\\,000$
• $1 \leq x\_i, y\_i \leq N$ ($1 \leq i \leq N-1$)
• 임의의 서로 다른 두 도시는 도로들을 통해 이동할 수 있다.
• $0 \leq A\_i \leq 10^9$ ($1 \leq i \leq N-1$)
• $1 \leq k\_i < N$ ($1 \leq i \leq Q$)
• $0 \leq v\_i \leq 10^9$ ($1 \leq i \leq Q$)
• 입력으로 주어지는 모든 수는 정수다.