Background

This is a classic problem.

Problem Description

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.

Input Format

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 Format

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

3 3
1 2 0
2 3 1
3 2 2

1

Hint

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