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

3 3
0 1 1
1 2 2
0 2 5

6

3 2
0 1 1
1 2 2

-1