P4234 Minimum Difference Spanning Tree

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.

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 a single integer on one line, which is the answer.

#### 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