Description

Given an undirected graph with vertices labeled from $1$ to $n$ and $m$ edges, find a spanning tree that minimizes the difference between the maximum and minimum edge weights in the tree. The graph may contain self-loops.

Input Format

The first line contains two integers, the number of vertices $n$ and the number of edges $m$.

Then follow $m$ lines. Each line contains three integers $u, v, w$, indicating there is an edge between $u$ and $v$ with weight $w$.

Output Format

Output a single integer on one line, which is the answer.

4 6 
1 2 10 
1 3 100 
1 4 90 
2 3 20 
2 4 80 
3 4 40 

20

Hint

Constraints and Conventions

• For $30\%$ of the testdata, it is guaranteed that $n \leq 100$, $m \leq 10^3$.
• For $97\%$ of the testdata, it is guaranteed that $n \leq 500$, $m \leq 10^5$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^4$, $1 \leq m \leq 2 \times 10^5$, $1 \leq u, v \leq n$, $1 \leq w \leq 10^4$.

Translated by ChatGPT 5