최악의 기자 4

Bitaro는 전문 기자로 프로그래밍 대회 기사를 쓴다. 며칠 뒤 국제 프로그래밍 대회가 열리고, Bitaro는 이 대회의 기사를 쓸 계획이다.

참가자는 1번부터 N번까지 N명이다. 각 참가자는 경쟁 프로그래밍에서의 실력을 나타내는 정수 레이팅을 가진다. 레이팅은 1 이상 1,000,000,000 이하의 정수이다.

Bitaro는 참가자들과 면담하여 다음 정보를 얻었다.

참가자 i (1 ≤ i ≤ N)의 레이팅은 참가자 Ai (1 ≤ Ai ≤ N)의 레이팅 이상이다. Ai = i인 경우도 있을 수 있다.

면담 후 Bitaro는 레이팅 관리 회사로부터 참가자들의 레이팅 목록을 받았다. 목록에는 다음 정보가 적혀 있다.

참가자 i (1 ≤ i ≤ N)의 레이팅은 Hi와 같다.

목록에는 오류가 있을 수 있다. Bitaro에게는 마감 전에 올바른 목록을 새로 받을 시간이 없다. 그래서 면담 정보와 모순되지 않도록 목록의 일부 레이팅을 바꾸기로 했다. 참가자 i의 레이팅을 바꾸는 데 드는 비용은 Ci이다. Bitaro는 Ci를 치르고 참가자 i의 레이팅을 1 이상 1,000,000,000 이하의 임의의 정수로 바꿀 수 있다. 그는 레이팅을 바꾸는 총비용을 최소로 하려 한다.

입력은 다음 형식으로 주어진다.

N
A1 H1 C1
.
.
.
AN HN CN

최소 총비용을 한 줄에 출력한다.

• 2 ≤ N ≤ 200,000
• 1 ≤ Ai ≤ N (1 ≤ i ≤ N)
• 1 ≤ Hi ≤ 1,000,000,000 (1 ≤ i ≤ N)
• 1 ≤ Ci ≤ 1,000,000,000 (1 ≤ i ≤ N)