The Hungary Games

Welcome to the Hungary Games! The streets of Budapest form a twisted network of one-way streets. As part of a reality TV show, you are forced to join a race through these streets, starting at the Szechenyi thermal bath ($s$ for short) and finishing at the Tomb of Gul Baba ($t$ for short).

Naturally, you want to finish as quickly as possible, because a better time earns you more promotional contracts. There is a catch, though: anyone clever enough to take a shortest $s$-$t$ route is thrown into the Palvolgyi cave system and kept there as a national treasure. You would like to avoid that fate while still being as fast as possible, so you must take a strictly second-shortest $s$-$t$ route.

Write a program that computes the length of a strictly second-shortest $s$-$t$ route. Note that such a route may sometimes visit some nodes more than once — for instance, by traversing the same edge back and forth.

The first line contains two integers $N$ and $M$, where $N$ is the number of nodes in Budapest and $M$ is the number of edges. The nodes are numbered $1, 2, \ldots, N$; node $1$ is $s$ and node $N$ is $t$.

Each of the next $M$ lines contains three integers $A\ B\ L$, describing a one-way street from $A$ to $B$ of length $L$. You may assume that $A \ne B$ on every line and that the ordered pairs $(A, B)$ are distinct.

Output the length of a strictly second-shortest route from $s$ to $t$ — that is, the second smallest value among the distinct total lengths of all routes from $s$ to $t$. If there are fewer than two distinct possible route lengths from $s$ to $t$, output $-1$.

Every length $L$ is a positive integer with $1 \le L \le 10000$. In 50% of the test cases, $2 \le N \le 40$ and $0 \le M \le 1000$. In all test cases, $2 \le N \le 20000$ and $0 \le M \le 100000$.