Minimum Edges to Remove to Form a Tree

You are given an undirected graph with n nodes and m edges. Each edge is described by three integers u, v, and w representing an edge between nodes u and v with weight w (the weight is not relevant for the connectivity).

Your task is to determine the minimum number of edges to remove to transform the graph into a tree. A tree is a connected acyclic graph, which for n nodes always has exactly n-1 edges.

If the graph is already disconnected (i.e. not all nodes are reachable) or if it is impossible to form a tree, output -1.

The answer is defined as follows:

• If n = 1, the answer is 0 because a single node is trivially a tree.
• If the graph is not connected, output -1.
• Otherwise, if there are redundant edges, the answer is m - (n - 1) (if any), otherwise, 0.

Note: The input will be read from standard input and the output should be printed to standard output.

inputFormat

The input is given via standard input and has the following format:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• n is the number of nodes,
• m is the number of edges,
• Each of the next m lines contains three integers u, v, and w, representing an edge between nodes u and v with weight w.

outputFormat

Output a single integer to standard output: the minimum number of edges to remove to transform the graph into a tree. If it is not possible to form a tree (i.e., the graph is disconnected), output -1.

## sample

5 6
1 2 2
1 3 1
2 3 2
2 4 3
3 5 1
4 5 3

2