You are given a graph with $n$ vertices. Initially, there are no edges.
You are given $m$ constraints. The $i$-th constraint is a triplet $(u_i, l_i, r_i)$, which means there is a directed edge from vertex $u_i$ to **every** vertex $v$ in the range $[l_i, r_i]$ (i.e., $l_i \le v \le r_i$).
The cost (weight) of the edge from $u_i$ to $v$ is $v - l_i + 1$.
Find the shortest path distance from vertex $1$ to all other vertices $1, 2, \ldots, n$.
#### Input
- The first line contains two integers $n$ and $m$ ($1 \leq n \leq 10^5, 1 \le m \le 2 \cdot 10^5$).
- The next $m$ lines each contain three integers $u, l, r$ ($1 \le u \le n, 1 \le l \le r \le n$).
#### Output
- Output $n$ integers. The $i$-th integer is the shortest distance from vertex 1 to vertex $i$.
- If a vertex is unreachable, output $-1$.
#### Subtasks
- **Subtask 1 (40%):** $n, m \le 2000$.
- **Subtask 2 (20%):** $n \le 4000$ and $m \le 2000$.
- **Subtask 3 (20%):** $n \le 4000$.
- **Subtask 4 (20%):** No additional constraints ($n \le 10^5, m \le 2 \cdot 10^5$).
#### Example
Input:
```
4 2
1 2 3
2 4 4
```
Output:
```
0 1 2 2
```
Explanation:
- From 1, we can go to 2 (cost $2-2+1=1$) or 3 (cost $3-2+1=2$).
- From 2, we can go to 4 (cost $4-4+1=1$).
- Dist(1) = 0.
- Dist(2) = 1.
- Dist(3) = 2.
- Dist(4) = Dist(2) + 1 = 2.
