Ethan was tasked with finding a minimum spanning tree of a weighted, connected, undirected graph. However, he misunderstood the task and found a spanning tree that may not be minimal. To make his spanning tree a minimum spanning tree, you perform a sequence of edge swaps. An edge swap removes one edge from the spanning tree and adds an edge from the graph which is not currently in the spanning tree. After each edge swap, the tree must still be a spanning tree. What is the minimum number of edge swaps you must perform to fix Ethan’s minimum spanning tree?
输入格式
The first line of input contains two integers () and (), where is the number of nodes in the graph and is the number of edges in the graph. The nodes are numbered from to .
Each of the next lines contains three integers , (), and (), signifying an edge connecting nodes and with weight . The edges are numbered from to .
It is guaranteed that the graph is connected. The first edges of the input are Ethan’s initial spanning tree. The graph may not be simple; there can be multiple edges between the same pair of nodes.
输出格式
Output a single integer , which is the minimum number of edge swaps needed to make the spanning tree a minimum spanning tree. Then output lines, each with two integers and , where is the number of the edge to remove and is the number of the edge to add. If there are multiple sets of edge swaps that work, any one will be accepted.
