Consider a undirected graph with $n$ vertices and $m$ edges, where each edge has a weight associated with it. Your task is to find the shortest path from vertex $1$ to vertex $n$. This shortest path should consist of the smallest possible number of edges and the sequence formed by edges weight must be lexicographically smallest among all paths with the same number of edges.
### Input
- The first line contains two integer $n,m$.
- The next $m$ lines, each line contains three integer $u,v,w$, there is an edge of weight $w$ from between $u$ and $v$.
### Output
- The first line, print an integer $k$, the length of the shortest path. It is guaranteed that the answer exists.
- The second line, print $k$ integers, the weight of edges on the path from $1$ to $n$.
### Constraints
- $1 \le n,m \le 10^5$.
- $1 \le u, v \le n, u \neq v$.
- $1 \le w \le 10^5$.
### Example
Input:
```
4 4
1 2 4
1 3 3
2 4 1
3 4 2
```
Output:
```
2
3 2
```
