A network operator wants to connect n sites, numbered 0 to n - 1, using exactly
n - 1 of the m available candidate links so that every site is connected to every other site
(directly or indirectly), and no candidate link is redundant (the chosen set forms a tree). Candidate
link i connects sites u and v at a cost of w; multiple candidate links between the same pair of
sites may exist, each counted as a distinct link.
Among all such valid networks (spanning trees), the cheapest one has some minimum total cost. Print the
SECOND smallest DISTINCT total cost achievable by a valid network -- that is, the smallest total cost
that is strictly greater than the minimum. If the sites cannot all be connected at all, or if every
possible valid network has the exact same total cost (so no second, larger, distinct cost exists),
print -1 instead.
Input format
Line 1: two integers n m.
Next m lines: three integers u v w -- an undirected candidate link between sites u and v
costing w (sites are 0-indexed).
Output format
A single integer: the second-smallest distinct total cost among all valid spanning networks, or -1
if it does not exist.
Constraints
- 2 <= n <= 16
- 0 <= m <= 60
- 0 <= u, v < n, u != v
- 1 <= w <= 1000