Under construction

Still being built. Things may change

Worst Reporter 4

Time limit2sMemory limit512 MB

Level

Not classified yet

Solved
No attempts yet

Problem

Bitaro is a professional reporter who writes reports on competitive programming contests. An international contest will be held in a few days, and Bitaro plans to write a report on it.

There are N contestants, numbered from 1 to N. Each contestant has an integer rating that measures their strength in competitive programming. A rating is an integer between 1 and 1,000,000,000, inclusive.

Bitaro interviewed the contestants and obtained the following information.

The rating of contestant i (1 ≤ i ≤ N) is greater than or equal to the rating of contestant Ai (1 ≤ Ai ≤ N). It is possible that Ai = i.

After the interviews, Bitaro received a list of contestant ratings from the company that manages the rating system. The list contains the following information.

The rating of contestant i (1 ≤ i ≤ N) is equal to Hi.

The list may contain errors. Bitaro has no time to obtain a correct list before the deadline, so he decided to change some ratings in the list so that the list does not contradict the interview information. Changing the rating of contestant i costs Ci. Bitaro can change the rating of contestant i to any integer between 1 and 1,000,000,000, inclusive, by paying Ci. He wants to minimize the total cost of the changes.

Input

The input is given in the following format.

N
A1 H1 C1
.
.
.
AN HN CN

Output

Print the minimum total cost on one line.

Constraints

  • 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)

Examples4

  1. Example 1

    Input
    6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
    Expected output
    14

  2. Example 2

    Input
    5
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1
    Expected output
    0

  3. Example 3

    Input
    20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
    Expected output
    2711043927

  4. Example 4

    Input
    20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030
    Expected output
    4012295156