Problem Q
Buenos Airlines

Alice och Bob fantiserar om en avlägsen framtida sommarsemester när de kan resa helt obehindrat, utan att behöva oroa sig för pandemier, pengar, eller andra planetära problem. Eftersom de älskar vintern hade de tänkt åka till södra halvklotet, närmare bestämt till Chile. Chile är ett ganska endimensionellt land (rent geografiskt alltså), och kan representeras som en oändligt lång $y$-axel. Det finns $N$ städer i Chile, numrerade från $1$ till $N$, där stad nummer $i$ är belägen vid $y$-koordinaten $y_ i$. Alice och Bob kommer börja sin resa i stad nummer $1$, och sedan vill de ta sig till någon annan stad.

Varje stad har en flygplats som det går att flyga till andra städer från. Men det går inte att flyga hur korta sträckor som helst: varje stad $i$ har en minimal flygsträcka $d_ i$ och det går bara att flyga direkt till städer $j$ som uppfyller $|y_ i - y_ j| \geq d_ i$. Tiden för själva flygturen är $|y_ i - y_ j|$ minuter, men det tar också tid att åka till flygplatsen, checka in, osv. Varje stad har alltså en extratid $r_ i$, och att flyga från $i$ till $j$ tar totalt $r_ i + |y_ i - y_ j|$ minuter.

Din uppgift är att hitta kortaste möjliga tiden att ta sig till var och en av de andra städerna, om Alice och Bob börjar vid stad nummer $1$. Det enda möjliga färdmedlet är flyg, men de kan flyga hur många gånger som helst.

Indata

Första raden innehåller ett heltal $N$ antalet städer ($2 \leq N \leq 2 \cdot 10^5$). Följande $N$ rader innehåller tre heltal var, $y_ i$, $d_ i$ och $r_ i$ ($0 \leq y_ i, d_ i, r_ i \leq 10^9$). Alla $y$-koordinater är olika.

Utdata

Skriv ut $N-1$ rader med ett heltal var. På den $i$:te raden ska du skriva ut kortaste möjliga tiden att ta sig till stad nummer $i+1$ om det är möjligt. Om det inte är möjligt ska du istället skriva ut $-1$.

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