Minimum Spanning Tree Range

Given an undirected graph with vertices labeled from 1 to n and m edges, possibly including self-loops, find the spanning tree whose range (i.e., the difference between the maximum edge weight and the minimum edge weight) is minimized.

A spanning tree is a subset of the graph's edges that connects all vertices without any cycles. Note that self-loops cannot be used in constructing a spanning tree.

The answer is the minimum achievable value of (max_edge_weight - min_edge_weight) among all valid spanning trees.

Hint: Consider sorting the edges by weight and using a sliding window technique combined with a union-find (disjoint set union) structure to check connectivity.

inputFormat

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

Each of the next m lines contains three integers u, v, and w, denoting an undirected edge between vertices u and v with weight w.

It is guaranteed that the vertices are labeled from 1 to n. The graph may have self-loops.

outputFormat

Output a single integer representing the minimum possible difference between the maximum and minimum edge weights in a spanning tree.

sample

4 5
1 2 3
2 3 4
3 4 5
4 1 6
2 4 7

2