Given an undirected, weighted graph of $n$ vertices and $m$ edges.
If your path from $u$ to $v$ consists of $k$ edges weigh $w_1,w_2,...,w_k$, then the final weight of the path is calculated as follow:
$$w_1+w_2+...+w_k-max(w_1,w_2,...,w_k)$$
Find the weight of the shortest path from $1$ to $n$.
### Input
- The first line contains 2 integers $n, m$.
- The next $m$ lines, each line contains 3 integers $u, v, w$, there is an edge of weight $w$ connecting $u, v$.
### Output
- Print the weight of the shortest path from $1$ to $n$, or print `-1` if no path exists.
### Constraints
- $1 \le n, m \le 2 \times 10^5$.
- $1 \le u, v \le n$.
- $1 \le w \le 10^9$.
### Example
Input:
```
3 3
1 2 1
2 3 2
1 3 3
```
Output:
```
0
```
