Almost Shortest Path

Bessie the cow is roaming a vast network of barns connected by bidirectional roads. Each barn is numbered from 1 to \(N\) and each road connects two barns with a given length, specified by \(c\) miles.

While Bessie knows the shortest path from barn 1 to barn \(N\), she is curious about an almost shortest path. This is defined as the second shortest path whose total length \(L\) satisfies:

\(\text{shortest y} < L \leq \text{shortest} + 5\)

Your task is to help determine the length of this almost shortest path. If no such path exists, output -1.

Note: Roads are undirected, and each road is described by three integers: the two barns it connects and the length between them.

inputFormat

The first line contains two integers \(N\) and \(M\) denoting the number of barns and the number of roads, respectively.

The next \(M\) lines each contain three integers \(a\), \(b\), and \(c\) indicating that there is a road connecting barn \(a\) and barn \(b\) with length \(c\) miles.

outputFormat

Output a single integer: the length of the almost shortest path from barn 1 to barn \(N\) that is strictly longer than the shortest path but no more than 5 miles extra. If no such path exists, output -1.

5 7
1 2 1
2 5 4
1 3 3
3 5 2
1 4 2
4 5 3
2 3 1

5