# Buenos Airlines

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.

Sample Input 1 | Sample Output 1 |
---|---|

5 1 3 2 2 5 2 3 0 0 4 2 4 5 3 0 |
9 -1 5 6 |

Sample Input 2 | Sample Output 2 |
---|---|

10 247 50 75 249 60 45 211 60 45 288 70 60 356 60 35 189 60 45 237 85 50 225 85 40 412 60 30 212 85 45 |
238 364 277 184 133 338 350 240 363 |