Minimum MEX Spanning Tree

Given an undirected connected graph with n vertices and m edges. Each edge has a weight. For any set S of natural numbers, its mex is defined as:

\(\text{mex}(S)=\min\{x\in \mathbb{N} : x \notin S\}\).

Your task is to select a spanning tree of the graph such that the mex of the set of its edge weights is as small as possible. In other words, if the set of weights in the spanning tree is \(W\), you must choose a spanning tree so that \(\text{mex}(W)\) is minimized.

Note: A spanning tree is a subset of the edges that connects all vertices with exactly \(n-1\) edges and without cycles.

inputFormat

The first line contains two integers n and m (\(2 \le n \le 10^5\), \(n-1 \le m \le 2\times10^5\)) — the number of vertices and edges.

Each of the next m lines contains three integers u, v and w (\(1 \le u,v \le n\), \(0 \le w \le 10^9\)), representing an edge between vertices u and v with weight w.

The graph is guaranteed to be connected.

outputFormat

On the first line output a single integer — the minimum possible mex value of the spanning tree obtained by your method.

Then output exactly n-1 lines. Each of these lines should contain two integers u and v, representing an edge in your spanning tree. If there are multiple solutions, any one is accepted.

sample

3 3
1 2 0
2 3 1
1 3 2

0
1 3
3 2