Your boss has left you in charge of ~N~ cities with ~M~ forests separating them. Each forest has a cost required to clear, and clearing a forest will merge the two cities it had once separated. He wants you to merge these ~N~ cities into ~x~ megacities, where the number of megacities satisfies ~x^2 - (N+1)*x + N = 0~. What is the minimum cost required to complete the job? If there are two minimum solutions, find the larger one.

Input Specifications

The first line will contain two integers, ~N~ and ~M (1 \leq N, M \leq 10^5)~, separated by a space.

The next ~M~ lines will contain three integers, ~A, B, C (1 \leq A, B \leq N, 1 \leq C \leq 10^7)~, the two cities separated by a forest and the cost to clear the forest, separated by spaces. ~A~ and ~B~ are guaranteed to be different from each other.

Output Specifications

Output the minimum cost required to complete the job, satisfying the conditions.

Subtasks

Subtask 1 [20%]

~N \leq 10^3~

~M \leq 10^3~

Subtask 2 [80%]

No additional constraints.

Sample Input 1

5 7
3 4 23
1 3 18
3 4 2
3 2 14
1 3 3
5 3 6
4 3 3

Sample Output 1

25

Sample Input 2

4 8
2 1 18
4 2 8
2 4 26
4 1 13
1 4 12
4 1 7
2 4 7
4 2 1

Sample Output 2

0