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

题目描述

C 国有 $N$ 个城市，通过 $M$ 条有偿道路相连。每条道路都有一个过路费。 为了促进贸易，国王决定修建一个连接所有城市的“皇家路网”（即一棵生成树）。 为了体现公平，国王希望路网中收费最高的道路与收费最低的道路之间的差值（极差）最小。 请输出这个最小的极差。如果无法连通所有城市，输出 -1。

输入格式

第一行两个整数 $N, M$。 接下来 $M$ 行，每行三个整数 $u, v, w$，表示一条双向道路。

输出格式

输出一个整数，表示最小极差。若无解输出 -1。

输入输出样例 #1

输入 #1

4 5
1 2 3
1 3 5
2 3 6
2 4 8
3 4 10

输出 #1

3

(解释：生成树若选 (1,2,3), (1,3,5), (2,4,8)，极差 8-3=5。若选 (1,3,5), (2,3,6), (2,4,8)，极差 8-5=3? 等等，(1,3,5),(2,3,6),(2,4,8) 无法连接1和2... 哦 1-3-2-4 连通。极差 8-5=3。 之前的样例解释可能有误，标程会算出最优解) (注：上例解释：选 (1,3,5), (2,3,6), (2,4,8) 可以连通所有点。5,6,8，差值3。对，3是最优)

数据范围

$1 \le N \le 100$， $1 \le M \le 2000$。