Given an undirected, weighted graph of $n$ vertices and $m$ edges. Find 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 on one line, then print the path on another line. Print `-1` if no solution exists. In case there are more than 1 solution, print any.
### 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:
```
3
1 2 3
```
