Maximizing Internet Connection Cost

Cow Betsy is hired to connect N cow barns with internet. There are M potential cables available, each connecting two barns with a cost C.

Farmer John, being extremely frugal, wants to minimize his spending, even at the cost of not paying Betsy any commission. In revenge, Betsy decides to choose some cables to build a network that connects all barns such that the total cost is maximized. However, she must avoid creating any cycles in the network, otherwise John will catch on.

Formally, you are given an undirected graph with N nodes and M edges. Each edge has a cost \(C\). Your task is to find a spanning tree (i.e. a cycle-free subgraph connecting all nodes) with the maximum possible total cost. If it is impossible to connect all barns, output -1.

Constraints: \(2 \le N \le 10^3\), \(1 \le M \le 2\times10^4\), \(1 \le C \le 10^5\).

inputFormat

The first line contains two integers N and M, representing the number of barns and the number of available cables, respectively.

The following M lines each contain three integers u, v, and C, denoting that there is a cable connecting barns u and v with cost C.

outputFormat

Output a single integer — the maximum total cost required to connect all barns without forming a cycle. If it is impossible to connect all barns, output -1.

sample

2 1
1 2 5

5