Problem G
Metro Lines

Pathland is a city arranged in a line. A single long tunnel runs across the city with multiple metro lines going back and forth across different portions of this tunnel.

There are $N+1$ stops numbered sequentially from $0$ to $N$ along the tunnel. There are also $M$ metro lines numbered $1$ through $M$ where the $i$’th metro line goes back and forth between stop $\ell _i$ and $r_i$ ($\ell _i < r_i$).

Each line charges a fare that is proportional to the number of stops it carries you. That is, the $i$’th metro line has a cost $c_i$ and charges you $c_i \cdot |x - y|$ to go between stops $x$ and $y$ (provided both $x$ and $y$ lie in the range $\{ \ell _i, \ell _i+1, \ldots , r_i\} $). You live near the left end of the city, meaning your nearest stop is $0$.

You want to know the cheapest way to get to any other stop. You can enter or exit any train at any stop in its range. You can even reboard a train you have already taken (see the second sample input). The time you may spend waiting for a train to reach you when waiting at a stop is not a consideration in this problem, you just want to know the cheapest way to reach each stop from stop $0$.

Input

The first line of input contains two integers $N$ ($1 \leq N \leq 200\, 000$) and $M$ ($1 \leq M \leq 200\, 000$). This means there are $N+1$ stops numbered $0$ through $N$ plus $M$ different metro lines.

Then $M$ lines follow, each describing a metro line. The $i$’th line contains three integers $\ell _i, r_i, c_i$ ($0 \leq \ell _i < r_i \leq N$ and $0 \leq c_i \leq 10\, 000$) describing the $i$’th metro line as above.

Output

Output $N$ lines. The $i$’th line contains the minimum total cost required to travel from stop $0$ to stop $i$. If it is not possible to reach stop $i$ using the existing metro lines, this line should contain a $-1$ instead.

5 3
0 3 5
2 4 1
1 5 7

5
10
11
12
19

6 2
0 4 2
1 3 1

2
3
4
6
-1
-1