불꽃놀이

불꽃놀이에서 가장 중요한 것은 스위치 하나에 도화선으로 연결된 폭약이 모두 같은 시각에 터지는 것이다. 폭약은 위험해서 스위치에서 멀리 떨어진 곳에 설치하고, 여러 조각의 도화선으로 스위치와 잇는다. 도화선은 트리의 간선이 이어지는 방식과 똑같이 이어져 있어서, 스위치 하나에 폭약 여러 개를 연결한다 [Figure 1].

스위치에서 생긴 불씨는 도화선을 따라 움직인다. 불씨가 도화선들이 만나는 연결점에 닿으면 그 연결점에 이어진 모든 도화선으로 퍼진다. 불씨가 움직이는 속도는 어디서나 같다. [Figure 1]에는 폭약 6개 E1, E2, ..., E6이 연결된 모습과 각 도화선의 길이가 나타나 있다. 괄호 안의 숫자는 시각 0에 스위치에서 불씨가 생겼다고 할 때 각 폭약이 터지는 시각이다.

[Figure 1] 연결 상태

불꽃놀이를 준비하는 현민이가 연결 상태를 하나 구성했다. 그런데 현민이가 만든 연결 상태로는 모든 폭약이 동시에 터지지 않을 수 있다. 그래서 도화선 몇 개의 길이를 늘이거나 줄여 모든 폭약이 같은 시각에 터지게 하려고 한다. 예를 들어 [Figure 1]의 폭약을 모두 시각 13에 터지게 하려면 [Figure 2]의 왼쪽처럼 길이를 조정하면 되고, 모두 시각 14에 터지게 하려면 [Figure 2]의 오른쪽처럼 조정하면 된다.

[Figure 2] 동시에 터지도록 도화선의 길이를 조정한 예

도화선 하나의 길이를 조정하는 비용은 조정 전후 길이 차이의 절댓값이다. [Figure 1]의 연결 상태를 [Figure 2]의 왼쪽처럼 바꾸면 비용은 6이고, [Figure 2]의 오른쪽처럼 바꾸면 비용은 5이다.

도화선의 길이를 0으로 줄일 수도 있다. 이때도 도화선의 연결 상태는 그대로 유지된다.

도화선의 연결 상태를 입력으로 받아, 모든 폭약이 동시에 터지도록 도화선의 길이를 조정하는 최소 비용을 출력하는 프로그램을 작성하라.

모든 입력 값은 양의 정수이다. 연결점의 수를 $N$, 폭약의 수를 $M$이라고 하자 ($1 \le N+M \le 300000$). 각 연결점에는 1부터 $N$까지, 각 폭약에는 $N+1$부터 $N+M$까지 번호가 붙어 있다. 스위치는 항상 1번 연결점이다.

입력은 다음과 같은 형태로 주어진다.

N M
P2 C2
P3 C3
...
PN CN
PN+1 CN+1
...
PN+M CN+M

첫째 줄에 $N$과 $M$이 주어진다. 다음 $N+M-1$개 줄에는 $i = 2, 3, \ldots, N+M$에 대해 두 정수 $P_i$와 $C_i$가 차례로 주어진다. $P_i$는 $i$번 연결점 또는 폭약이 도화선으로 연결된 연결점의 번호이고 ($1 \le P_i \le i$), $C_i$는 그 도화선의 길이이다 ($1 \le C_i \le 10^9$).

1번을 제외한 각 연결점에는 도화선이 2개 이상 연결되어 있다. 즉 스위치 쪽 도화선 하나와 그 아래쪽 도화선 하나 이상이 이어져 있다. 각 폭약에는 도화선이 정확히 하나 연결되어 있다.

모든 폭약이 동시에 터지도록 도화선의 길이를 조정하는 최소 비용을 출력한다.