Marisa's got $n$ apple trees, more than she can handle on her own. She really wants to pick all the apples, but it's just too much work. So, she's hired Nitori to give her a hand with the harvest.
Nitori offers $q$ different services to help Marisa with her apple trees. Each service $i$ has a specific cost of $c_i$ coins to harvest all the trees between numbers $l_i$ and $r_i$. Marisa wants to know what's the cheapest cost get all her apples harvested. Can you figure it out?
### Input
- The first line contains 2 integers $n, q$.
- The next $q$ lines, each line contains either $l_i, r_i,c_i$, a service.
### Output
- Print the minimum cost. If there is no way to harvest all the apples, print `-1`.
### Constraints
- $1 \le n, q\le 10^5$.
- $1 \le l_i, r_i \le n$.
- $1 \le c_i \le 10^9$.
### Example
Input:
```
5 3
1 4 2
5 5 3
2 5 1
```
Output:
```
3
```
