## Maximum Deviation Spanning Tree

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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

, , .
, , .
.
, and .
, and is an odd number.

#### 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.