Given a sequence , the deviation of the sequence is defined as the minimal value of
, where
can be any real number. For example, the deviation of
is
, which can be achieved when we choose
.
Similarly, given a tree, the tree's deviation is defined as the deviation of the tree's edge weight sequence. Now, given a connected graph, please write a program to find a spanning tree with the maximal deviation.
Note, there may be multiple edges between the same pair of vertices.
Input Specification
The first line of input contains two integers, and
(
,
), indicating the number of vertices and the number of edges in the given graph.
Each of the following lines contains three integers
,
and
(
,
), indicating an undirected edge between
and
with a cost of
.
Output Specification
Output one integer, the max deviation of the spanning tree.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
No additional constraints. |
Sample Input
4 6
1 2 1
1 3 2
2 3 5
3 2 4
2 4 3
3 4 2
Sample Output
4
Explanation
A possible spanning tree with the max deviation is to choose the st,
rd, and
th edges.
Comments