Macduff, after a long and excruciating fight against Macbeth, seeks to return to his orginal location and time period as soon as possible to avoid any further distruptions in history. However, Macbeth has set a blatant trap that will stop Macduff from returning home if he chooses any of the strictly shortest paths back home. Macduff, wanting to get home as soon as possible without getting trapped, asks you for your help to find the strictly second shortest path back home.

Input Specification

The first line of input will contain space separated positive integers ~N~ and ~M~, where ~N~ represents the number of portals (labelled as ~1,2,3...,N~), ~M~ represents the number of weighted directed edges, and ~1~, ~N~ are the starting and ending portals respectively. Portals can travel to more than one other portal. You may visit the same node more than once. You may go to node ~N~ and leave it before returning again as a path.

The next ~M~ lines of input will contain space separated positive integers ~a, b, d~, ~(1 \le a,b \le N)~, which represents an directed edge of weight ~d~ from ~a~ to ~b~.

Output Specification

Output the length of the strictly second shortest path through the portals. If there is no strictly second shortest path, output ~-1~.

Hint: Consider the shortest path through the portals and each edge in the shortest path. How can you determine the second shortest path using this?

Subtasks

Subtask 1 [10%]

~2 \le N \le 5~

~1 \le M \le 15~

~1 \le d \le 10~

Subtask 2 [20%]

~2 \le N \le 100~

~1 \le M \le 500~

~1 \le d \le 100~

Subtask 3 [70%]

~2 \le N \le 10^4~

~1 \le M \le 10^5~

~1 \le d \le 10^3~

Sample Input 1

5 10
1 5 10
1 4 4
3 4 7
5 1 2
1 2 8
4 1 1
2 3 9
5 2 3
3 1 3
4 3 10

Sample Output 1

15

Explanation 1

There are many different paths from portal ~1~ to portal ~5~, with distances (sortest least to greatest) ~[10, 15, 20, 22, ...]~. The second shortest path has length ~15~ (node ~1~ to node ~4~ to node ~1~ to node ~5~).

Sample Input 2

4 4
1 2 2
1 3 3
1 4 4
2 3 1

Sample Output 2

-1

Explanation 2

There is only one path from portal ~1~ to portal ~4~, so there is no second shortest path.