Given a sequence ~A = [a_1, a_2, \ldots, a_n]~, the deviation of the sequence is defined as the minimal value of ~\sum_{i}{|a_i - x|}~, where ~x~ can be any real number. For example, the deviation of ~[2, 1, 4]~ is ~3~, which can be achieved when we choose ~x=2~.

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, ~N~ and ~M~ (~2 \le N \le 2 \times 10^5~, ~1 \le M \le 5 \times 10^5~), indicating the number of vertices and the number of edges in the given graph.

Each of the following ~M~ lines contains three integers ~u_i~, ~v_i~ and ~w_i~ (~1\le u_i, v_i \le N~, ~1 \le w_i \le 10^9~), indicating an undirected edge between ~u_i~ and ~v_i~ with a cost of ~w_i~.

Output Specification

Output one integer, the max deviation of the spanning tree.

Constraints

Subtask	Points	Additional constraints
~1~	~15~	~N \le 10~, ~M \le 20~, ~w_i \le 100~.
~2~	~15~	~N \le 100~, ~M \le 100~, ~w_i \le 100~.
~3~	~20~	~N, M \le 1\,000~.
~4~	~10~	~N, M \le 10^5~, and ~N = M~.
~5~	~15~	~N, M \le 10^5~, and ~N~ is an odd number.
~6~	~25~	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 ~1~st, ~3~rd, and ~6~th edges.