곤경에 빠진 댐

풍요와 비와 수확의 신인 프레이르는 요즘 골치가 아프다. 거인들이 다시 미드가르드를 침략하려 하고, 미드가르드로 이어지는 여러 계곡의 아래쪽에 전쟁 진영을 세웠다. 프레이르는 그 진영을 쓸어버려야 승리의 잔치를 열 수 있다. 계곡 아래쪽에 있으니, 이 지역에 비가 내리면 강과 개울을 따라 계곡 아래쪽까지 흘러가 거인들을 물에 잠기게 하는 데 보탬이 된다. 하지만 비버와 부지런한 인간들이 하천 곳곳에 댐을 지었고, 이 댐들은 일정량의 물을 담아 두는 완충 역할을 한다. 반대로 댐이 용량까지 차면 무너져서, 거기 저장된 물 전부와 그 뒤에 더해지는 물까지 아래쪽으로 방류된다.

비의 신인 프레이르는 전쟁 진영을 쓸어버리는 데 필요한 물의 양을 정확히 알고 있고, 각 댐의 정확한 용량과 현재 저장된 물의 양도 알고 있다. 풍요와 수확의 신이기도 한 프레이르는 하루 종일 사방에 비를 내릴 일이 없으므로, 한 곳(댐 하나 또는 전쟁 진영)에만 비를 내리기로 하고, 그 한 곳에 내리는 비의 양을 최소로 하려 한다. 프레이르가 비를 내릴 최적의 장소를 잘 고를 때, 거인들의 전쟁 진영을 쓸어버리는 데 필요한 최소 강수량은 얼마인가?

댐들과 전쟁 진영은 뿌리 있는 트리를 이루며, 전쟁 진영이 뿌리이고, 댐의 부모는 그 댐의 바로 아래쪽에 있는 위치(다른 댐 또는 전쟁 진영)이다. 예는 그림 1을 보라.

그림 1: 예제 입력 1의 그림. 이 경우 프레이르는 가장 왼쪽 댐에 $2$만큼 비를 내려 그 댐을 무너뜨리고 $50$만큼의 물을 아래쪽으로 보내면 되고, 그 결과 최종적으로 $100$만큼의 물이 전쟁 진영에 도달해 진영을 잠기게 하는 데 필요한 $75$를 훨씬 넘는다.

입력의 첫 줄에는 두 정수 $n$과 $w$가 주어진다($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^9$). 각각 댐의 수와 전쟁 진영을 쓸어버리는 데 필요한 물의 양이다. 이어서 $n$개의 줄에 걸쳐 $n$개의 댐을 설명한다. 댐은 $1$부터 $n$까지 번호가 매겨진다.

$i$번째 줄에는 세 정수 $d_i$, $c_i$, $u_i$가 주어진다($0 \le d_i < i$, $1 \le c_i \le 10^9$, $0 \le u_i < c_i$). $d_i$는 댐 $i$의 바로 아래쪽에 있는 댐의 번호이고(댐 $i$의 바로 아래쪽이 전쟁 진영이면 $0$), $c_i$는 댐 $i$의 최대 용량, $u_i$는 댐 $i$에 현재 저장된 물의 양이다.

한 곳에 비를 내려 전쟁 진영에 적어도 $w$만큼의 물이 도달하게 하는 데 필요한 최소 강수량을 출력한다.