A transit map has n stations, numbered 0 to n - 1, connected by m two-way tracks.
Track i connects stations u and v and takes w minutes to ride. A "route" from station s to
station t is a sequence of tracks that never revisits a station (a simple path).
Different routes can share the same total travel time. Print the SECOND smallest DISTINCT total travel
time among all routes from s to t (that is, the smallest travel time that is strictly greater than
the minimum possible travel time). If t is unreachable from s, or if every route from s to t
shares the exact same total travel time (so no second, larger, distinct value exists), print -1
instead.
Input format
Line 1: two integers n m.
Next m lines: three integers u v w -- an undirected track between stations u and v taking w
minutes (stations are 0-indexed).
Last line: two integers s t, with s != t.
Output format
A single integer: the second-smallest distinct total travel time among all simple routes from s to
t, or -1 if it does not exist.
Constraints
- 2 <= n <= 16
- 0 <= m <= 60
- 0 <= u, v < n, u != v
- 1 <= w <= 1000
- 0 <= s, t < n, s != t