C. mansion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are the owner of a new mansion and you want to navigate it efficiently.

The mansion has $$$N$$$ rooms connected by $$$M$$$ one-way security doors. Each door opens only in the specified direction. Every door is either locked or unlocked. Traversing an unlocked door takes $$$0$$$ time units and traversing a locked door takes $$$1$$$ time unit. You have a badge that allows you to open any locked door.

Your goal is to travel from room $$$1$$$ to room $$$N$$$ with the minimum total time.

Input

The first line contains two integers $$$N$$$ ($$$2 \leq N \leq 10^5$$$) and $$$M$$$ ($$$1 \leq M \leq 10^5$$$) — the number of rooms and the number of doors.

Each of the next $$$M$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq N$$$, $$$u_i \neq v_i$$$), and $$$t_i$$$ ($$$t_i\in\{0,1\}$$$) — describing a door. The door leads from room $$$u_i$$$ to room $$$v_i$$$, and $$$t_i$$$ is the traversal time of the door, where $$$0$$$ means unlocked and $$$1$$$ means locked.

Output

Output one integer — the minimum total time required to reach room $$$N$$$ from room $$$1$$$, or $$$-1$$$ if room $$$N$$$ is not reachable.

Examples
Input
5 6
1 2 0
2 3 1
3 5 0
1 4 1
4 5 1
2 5 1
Output
1
Input
3 2
1 2 1
2 1 1
Output
-1