题目描述

给你一张简单无向连通图，边权都为非负整数。你需要求出这幅图的所有生成树中，边权最大的边的边权与边权最小的边的边权的差值最小是多少。

图用以下形式给出：

第一行输入两个整数 $n,m$，表示图的顶点数、边数，顶点编号从 1 到 $n$。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 与 $y$ 之间有一条边，边权为 $z$。

请输出最小边权差。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行有三个整数，代表一条边。

输出格式

输出一个数表示答案。

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

2

数据规模

对于所有数据，保证 $2≤n≤5000,n−1≤m≤8000,1≤x,y≤n,x≠y,1≤z≤10000$。