신호기

$N$개의 정점과 가중치가 있는 간선으로 이루어진 트리가 주어진다. 트리에서 두 정점 사이의 거리를 두 정점을 연결하는 단순 경로상에 있는 간선의 가중치의 합으로 정의하자.

각 정점에는 신호기를 설치할 수 있다. 정점 $i$에 신호기를 설치하는 비용은 $A\_i$이며, 해당 신호기는 정점 $i$로부터의 거리가 $B\_i$ 이하인 모든 정점에 신호를 전파한다. 즉, 신호기를 설치한 정점은 항상 신호를 수신한다.

여러분은 모든 정점이 하나 이상의 신호기로부터 전파를 받도록 신호기를 설치해야 한다. 신호기를 설치하는 비용의 합의 최솟값을 구하여라.

첫째 줄에 정점의 개수 $N$이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐, $i$번째 줄에 두 정수 $A\_i$, $B\_i$가 공백으로 구분되어 주어진다.

그다음 줄부터 $N-1$개의 줄에 걸쳐 간선의 정보가 주어진다. 각 줄에는 세 정수 $u\_i$, $v\_i$, $w\_i$가 주어지며, 이는 $u\_i$번 정점과 $v\_i$번 정점이 가중치가 $w\_i$인 간선으로 연결되어 있음을 의미한다.

모든 정점이 하나 이상의 신호기로부터 전파를 받도록 신호기를 설치하기 위한 최소 비용을 출력한다.

• $2 \leq N \leq 100\\,000$
• $0 \leq A\_i \leq 10^9$
• $0 \leq B\_i \leq 2 \times 10^{14}$
• $1 \leq u\_i, v\_i \leq N$
• $1 \leq w\_i \leq 10^9$
• 입력으로 주어진 그래프는 트리다.
• 입력으로 주어진 모든 수는 정수다.