세계 정복

으하하하하하!!! 숙적인 미남 스파이 와코 파워스가 마침내 화산 비밀 기지의 함정에 걸려 최후를 맞았다 (직접 확인할 만큼 한가하지는 않았으니 그렇게 믿기로 한다). 드디어 세계를 정복할 준비가 끝났다!

앞을 가로막을 것은 없다. 물류라는 사소한 문제 하나만 빼면. 사악한 군대는 보수를 받지 못하면 세계의 하찮은 나라를 짓밟는 진군을 계속하지 않겠다고 선언했다. 게다가 자금도 바닥나고 있다. 화산 기지에는 훌륭한 점이 많지만 "적당한 가격"은 그중에 없다. 배은망덕한 부하에게 줄 돈을 마련하느라 이동 예산까지 헐어 썼다. 이제 군대를 어떻게 배치 지점까지 옮겨서 세계를 정복할지 막막하다.

세계 각국의 지도와 나라 사이를 잇는 이동 경로가 모두 있다. 각 경로는 두 나라를 잇고, 그 경로를 지나는 군대 한 부대마다 정해진 비용이 든다. 경로는 어느 두 나라 사이에도 이동 방법이 정확히 하나만 있도록 놓여 있다. 각 군대의 현재 위치와, 각 나라를 굴복시키려면 그 나라에 최종적으로 몇 부대를 남겨야 하는지도 알고 있다. 세계를 정복하려면 군대를 어떻게 옮겨야 비용이 가장 적게 드는가?

첫째 줄에 나라의 수 $n$이 주어진다 ($1 \le n \le 250000$). 다음 $n-1$개 줄에는 세 정수 $u$, $v$, $c$가 주어진다 ($1 \le u, v \le n$, $1 \le c \le 10^6$). 나라 $u$와 나라 $v$를 잇는 양방향 경로가 있고, 군대 한 부대가 이 경로를 지나는 데 비용 $c$가 든다는 뜻이다.

이어서 $n$개 줄이 주어진다. $i$번째 줄에는 음이 아닌 두 정수 $x_i$와 $y_i$가 있다. 현재 나라 $i$에 군대 $x_i$부대가 있고, 최종 배치에서 나라 $i$에 적어도 $y_i$부대가 남아 있어야 한다는 뜻이다. 군대의 총수, 곧 $x_i$의 합은 $y_i$의 합 이상이고 $10^6$ 이하이다.

모든 $i$에 대하여 나라 $i$에 군대가 $y_i$부대 이상 남도록 옮길 때, 드는 비용의 최솟값을 출력한다.