You are given a weighted undirected graph. The vertices are enumerated from 1 to $*n*$. Your task is to find the shortest path between the vertex $1$ and the vertex $*n*$.

Input

The first line contains two integers $*n*$ and $*m*$ ($2 ≤ *n* ≤ 10^{5}, 0 ≤ *m* ≤ 10^{5}$), where $*n*$ is the number of vertices and $*m*$ is the number of edges. Following $*m*$ lines contain one edge each in form $*a*_{*i*}$, $*b*_{*i*}$ and $*w*_{*i*}$ ($1 ≤ *a*_{*i*}, *b*_{*i*} ≤ *n*, 1 ≤ *w*_{*i*} ≤ 10^{6}$), where $*a*_{*i*}, *b*_{*i*}$ are edge endpoints and $*w*_{*i*}$ is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

Output

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.