A tourist board wants the shortest round trip in a park. The park has n viewpoints 0 .. n-1 and
undirected trails trails[i] = [u, v, metres] (metres >= 0). A loop is a walk that starts and
ends at the same viewpoint, uses at least one trail, and never uses the same trail twice or visits
a viewpoint twice (other than returning to the start). Two parallel trails between the same pair form
a loop; a trail from a viewpoint to itself is a loop on its own.
Return the length of the shortest loop, or -1 if the park has none.
Examples
Input: n = 4, trails = [[0,1,1],[1,2,1],[2,0,5],[2,3,1],[3,0,1]]
Output: 4
Explanation: 0 -> 1 -> 2 -> 3 -> 0 has length 4; the triangle 0-1-2 has length 7.
Input: n = 3, trails = [[0,1,3],[1,2,4]]
Output: -1
Input: n = 2, trails = [[0,1,3],[0,1,4]]
Output: 7
Constraints
1 <= n <= 200,0 <= len(trails) <= 400,0 <= metres <= 10**4- Target
O(E * E log V)time.
Goals
- Relate the shortest cycle through an edge to a shortest path without it
- Run a pruned Dijkstra per edge
- Treat self-loops and parallel roads as legitimate cycles