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

, , . | ||

, , . | ||

. | ||

, and . | ||

, and is an odd number. | ||

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