King kobortor, the ruler of HillThorn, feels the infrastructure in his country is too old. So, he wants to upgrade the infrastructure. HillThorn is a country with ~N~ cities (~1 \le N \le 1\,000~), and ~M~ (~1 \le M \le 5\,000~) bidirectional roads, where the ~i^{th}~ road connects cities ~u_i~ and ~v_i~ (~1 \le u_i, v_i \le N~) with weight ~w_i~ (~1 \le w_i \le 1\,000~). There may be multiple roads between cities ~u_i~ and ~v_i~. Suppose that the country is connected. The cost of bad infrastructure is the weight of the largest road in the country. King kobortor has the superpower to upgrade the roads around a city to weight ~0~. However, using this superpower on ~k~ cities will cost ~10k^2~. Please help King kobortor to find out the minimum sum of costs. The sum of costs includes the cost of the largest road and the cost of using the superpower.

Constraints

For all subtasks:

~1 \le N, w \le 1\,000~

~1 \le M \le 5\,000~

Subtask	Points	Additional constraints
~1~	~13~	~N \le 15~
~2~	~17~	~w \le 10~
~3~	~23~	~w \le 90~
~4~	~47~	No additional constraints.

Input Specification

The first line contains two integers, ~N~ and ~M~, the number of cities and the number of roads.

Each of the following ~M~ lines contains three integers, ~u~ ~v~ and ~w~, a road connecting cities ~u~ and ~v~ with weight ~w~.

Output Specification

One integer, the minimum sum of costs.

Sample Input 1

2 1
1 2 58

Sample Output 1

10

Sample Input 2

6 10
5 6 901
2 6 173
3 5 610
3 5 598
1 5 142
1 2 699
1 5 904
2 4 633
3 6 6
1 4 573

Sample Output 2

96

Explanation for Sample Output

In the ~1^{st}~ sample case, King kobortor can apply the superpower on city ~1~ or ~2~ to get a total cost of ~10~.

In the ~2^{nd}~ sample case, King kobortor can apply the superpower on cities ~1~, ~2~, and ~5~ with a cost of ~90~ and then the largest road is between cities ~3~ and ~6~ with a cost of ~6~. Thus the total cost is ~96~.