该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

本题需要使用文件重定向，输入文件名mdt.in，输出文件名mdt.out

题目描述

给定一个无向图，求它的一棵生成树，使得生成树中的最大边权与最小边权的差最小，输出 其最小差值。

输入格式

第一行两个整数$n，m$,分别表示点数和边数。

接下来$m$行，第i+1 行包含三个整数$X_i,Y_i,D_i$，表示有一条边连接$X_i$和$Y_i$，距离为$D_i$。

保证图是连通的，两个点之间最多只有一条边。

输出格式

包含一行，表示最小差值生成树的最大边与最小边的差值。

样例

3 3
1 2 10
1 3 20
2 3 30

10

数据范围

• 30%：$n,m\leq10$
• 60%：$n,m\leq1000$
• 100%：$2<n\leq200，m\leq5000, 0<X_i\leq n,0<Y_i\leq n,0<D_i\leq10^8$

来源

BY 粟科钞