1124. CGY 的安排

难敲杯国决终于结束了!好不容易来一趟京城,一行人决定去观光旅游景点,他们选择了一些必须要去的名胜。但是队长 HYR 的认路能力实在信不过,于是 Dr.Su 把安排路线的任务交给号称“人形自走 GPS”的 CGY。可是 CGY 第二天要去和自己的高中同学聚会,所以安排的路线规划必须尽可能的简单以使得路痴队长 HYR 能记住。

以下是 HYR 的要求:在能到达所有景点的基础上,选择尽可能少的道路,以便他记住的道路条数尽可能少。在此基础上,为了保证心理差距不要太大,路的长度区间必须尽可能的小,即要求最长的路和最短的路的长度差最小。

CGY 忙于联系自己的高中基友,并没有足够的时间搞这个,于是又把任务丢给了你,并答应事成之后请你喝北京名特产豆汁儿。

输入

输入包括多组样例(保证 1 \leq T≤1000),直到输入 0 0 为止。

每组样例格式如下:

n \ m
A_1 \ B_1 \ W_1
... \ ... \ ...
A_m \ B_m \ W_m

其中,所有输入均为整数,n \ (2≤n≤100) 表示景点个数,m \ (0≤m≤ \frac{n \times (n-1)}{2}) 表示可选道路数量。A_i,B_i \ (1 \leq n \leq n) 表示第 i 条边连接的两个景点序号。W_i \ (1 \leq W_i≤10000) 表示第 i 条道路的长度。输入保证不存在自环边(连接同一个景点的道路)或平行边(两条连接同样两个景点的道路)。

输出

对于每组样例,如果能找到这种路线规划,则输出最长的路和最短的路的长度差。否则,输出 -1

样例

标准输入 复制文本
4 5
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7
4 6
1 2 10
1 3 100
1 4 90
2 3 20
2 4 80
3 4 40
2 1
1 2 1
3 0
3 1
1 2 1
3 3
1 2 2
2 3 5
1 3 6
5 10
1 2 110
1 3 120
1 4 130
1 5 120
2 3 110
2 4 120
2 5 130
3 4 120
3 5 110
4 5 120
5 10
1 2 9384
1 3 887
1 4 2778
1 5 6916
2 3 7794
2 4 8336
2 5 5387
3 4 493
3 5 6650
4 5 1422
5 8
1 2 1
2 3 100
3 4 100
4 5 100
1 5 50
2 5 50
3 5 50
4 1 150
0 0
标准输出 复制文本
1
20
0
-1
-1
1
0
1686
50

来源

2018 软件学院蓝桥杯热身赛 (For 16/17)

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 71
通过 21