Broken Minimum Spanning Tree

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 that 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 contains two integers $n$ ($2 \le n \le 2\,000$) and $m$ ($n-1 \le m \le 3\,000$), where $n$ is the number of nodes and $m$ is the number of edges. The nodes are numbered from $1$ to $n$.

Each of the next $m$ lines contains three integers $u$, $v$ ($1 \le u,v \le n$, $u \ne v$), and $w$ ($1 \le w \le 10^9$), meaning an edge connects nodes $u$ and $v$ with weight $w$. The edges are numbered from $1$ to $m$.

The graph is connected. The first $n-1$ edges are Ethan's initial spanning tree. The graph may not be simple, so there can be multiple edges between the same pair of nodes.

Output a single integer $k$, the minimum number of edge swaps needed to make the spanning tree a minimum spanning tree. Then output $k$ lines, each with two integers $a$ and $b$, where $a$ is the number of the edge to remove and $b$ is the number of the edge to add. If several sets of $k$ swaps work, any one is accepted.