Given an undirected, weighted graph of $n$ vertices and $m$ edges. Find the weight of the shortest path from $1$ to $n$ if you can apply the following operation at most $k$ times:
- Assign $0$ weight to an arbitrary edge.
### Input
- The first line contains 3 integers $n, m, k$.
- 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$.
- $1 \le k \le 5$.
### Example
Input:
```
3 3 1
1 2 1
2 3 2
1 3 3
```
Output:
```
0
```
