Blistavost

In the heart of the Glass Valley lies a mysterious star temple, known for its collection of magical crystals that shine like stars. Each crystal holds special power and emits a radiant glow that lights up the entire valley, as long as it stays untouched.

Every night, the temple guardian must touch ONLY the crystals inside the ranges requested by the valley's residents, and must satisfy all of their requests. Each request names a range of crystals that must NOT stop shining before the resident's bedtime, because the residents are afraid of the dark.

The guardian starts at the temple entrance and must plan the route so that each crystal stops shining at the right moment. The crystals are placed in a line, one meter apart, and the first crystal is one meter from the entrance. The guardian moves at one meter per second and may stop whenever needed. Touching and dimming a crystal takes no time. The guardian does not have to return to the starting position.

Find the minimum number of seconds needed to satisfy all requests.

The first line contains an integer $N$ ($1 \le N \le 5000$), the number of requests.

Each of the next $N$ lines contains integers $l_i$, $r_i$, and $t_i$ ($1 \le l_i \le r_i \le 10^{18}$, $1 \le t_i \le 10^{18}$), the left and right bounds of the crystal range and the resident's bedtime.

Output the minimum time in seconds needed to fulfill all the requests, on a single line.