P5631 Minimum MEX Spanning Tree

This is a classic problem.

Given an undirected connected graph with $n$ vertices and $m$ edges, each edge has a weight. Define the $\text{mex}$ of a set of natural numbers $S$ as the smallest natural number that does not appear in $S$. Now you need to find a spanning tree of this graph such that the $\text{mex}$ of the set of its edge weights is as small as possible.

The first line contains two positive integers $n, m$. The next $m$ lines each contain three non-negative integers $u, v, w$, indicating that there is an edge between $u$ and $v$ with weight $w$.

Output one line with one natural number, representing the minimum possible $\text{mex}$ value.

Constraints - For $20\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 200$. - For $50\%$ of the testdata, $1 \le n \le 2000$, $1 \le m \le 3000$. - For $80\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$. - For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le m \le 2 \times 10^6, 0 \le w \le 10^5$. The input size is large, so an efficient input method is recommended. Translated by ChatGPT 5