Problem K
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.

5
1 3 2
2 5 2
3 0 0
4 2 4
5 3 0

9
-1
5
6

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