Alice and Bob dream about future summer vacations where travel is unconstrained by pandemics, budgetary constraints, or other mundane problems. Since they love winter, they want to visit the Southern Hemisphere, in particular Chile. Chile is, geographically speaking, a rather one-dimensional country, and can be represented as an infinitely long $y$-axis. There are $N$ cities in Chile, numbered from $1$ to $N$, where the $i$th city is located at $y$-coordinate $y_ i$. Alice and Bob will start their journey in city number $1$, and travel to some other city from there.

Each city has an airport with a direct connection to other cities. However, flights cannot be arbitrarily short: For each city $i$ there is a minimal distance $d_ i$ such that there is a flight to city $j$ if and only if $|y_ i-y_ j|\geq d_ i$. The time for a flight is $|y_ i - y_ j|$ minutes, but it also takes time to travel to the airport, check in, pass security, etc. Thus, for each city there is an additional time $r_ i$ such that the total time to fly from $i$ to $j$ is $r_ i + |y_ i - y_ j|$ minutes.

Find the shortest possible time to get to each of the other cities, provided that Alice and Bob start in city $1$. Flights are the only means of transportation, but Alice and Bob can take as many flights as they like.

-----Input-----
The first line contains an integer $N$, the number of cities, where $2 \leq N \leq 2 \cdot 10^5$. The following $N$ lines each consist of three integers $y_ i$, $d_ i$, and $r_ i$, where $0 \leq y_ i, d_ i, r_ i \leq 10^9$. All $y$-coordinates are distinct.

-----Output-----
Print $N-1$ lines, each containing an integer. On the $i$th line, print the shortest possible total time for getting from city 1 to city $i+1$, if possible. If there is no way to get to city $i+1$, print $-1$ instead.

-----Examples-----
Sample Input:
5
1 3 2
2 5 2
3 0 0
4 2 4
5 3 0
Sample Output:
9
-1
5
6

Source: kattis | Difficulty: HARD


Solutions: