时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
ZYB likes doing exercises, especially playing basketball.
ZYB's playground can be described as an undirected connected graph G with n nodes named from 1 to n and m edges )
,where 
is the length for this edge.
ZYB wants to jump between all pairs (i,j). If he starts at i,and wants to finish at j, he will choose the path for which the second longest edge is smallest, and denote its length as D(i,j). Besides, if a path contains only one edge, the length of second longest edge will be 0.
For example, if there 4 nodes and 4 edges (1,2,3),(2,4,4),(1,3,5),(3,4,2) and ZYB wants to jump from 1 and finish at 4. There are two possible paths 1-2-4(value=3),1-3-4(value=2), thus ZYB will choose 1-3-4 and D(1,4) will be 2.
Now ZYB wants to calculate)
, please help him.
ZYB wants to jump between all pairs (i,j). If he starts at i,and wants to finish at j, he will choose the path for which the second longest edge is smallest, and denote its length as D(i,j). Besides, if a path contains only one edge, the length of second longest edge will be 0.
For example, if there 4 nodes and 4 edges (1,2,3),(2,4,4),(1,3,5),(3,4,2) and ZYB wants to jump from 1 and finish at 4. There are two possible paths 1-2-4(value=3),1-3-4(value=2), thus ZYB will choose 1-3-4 and D(1,4) will be 2.
Now ZYB wants to calculate
输入描述:
The input only contains one test case.The first line contains two integers, describing the number of nodes and edges.
For the nextlines, each line contains three integers
, describing an edge between
and
with length
It is guaranteed that.
输出描述:
The input only contains one line indicating the answer.