A relay grid is a weighted undirected graph of n nodes (numbered 0 to n-1) joined by m cables, each with a positive integer length.
The weighted diameter of the grid is the largest shortest-path distance taken over every pair of distinct nodes. Compute it. If the grid is disconnected (some pair of nodes has no connecting path), report that the diameter is undefined. If n is 1 there are no pairs, so the diameter is 0.
Input format
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a cable between nodes u and v of length w.
Output format
A single integer: the weighted diameter, or -1 if the graph is disconnected.
Constraints
- 1 <= n <= 300
- 0 <= m <= 20000
- 0 <= u, v <= n-1
- 1 <= w <= 100000
- There may be multiple cables between the same pair of nodes; use the shortest.