penguinislands

There are N islands of penguins. Due to global warming, penguins now are finding it uncomfortable swimming between islands. Thus, they plan to build some bridges between the islands. However, since it is not that uncomfortable, they do not intend to spend money connecting all the islands. Thus, they have decided on a compromise. They will build bridges between the four largest islands, conveniently numbered from 1 to 4. However, due to strange penguin laws (that sometimes transcend the laws of physics), bridges can only be built between certain islands, and every possible bridge has a different cost to build. Help the penguins find the minimum cost to build bridges that ensure that islands 1 to 4 are all connected. Two islands are called connected if it is possible to get from one to another without swimming (i.e., only using bridges).

Input

The first line of input contains two integers N and E (4 ≤ N ≤ 200, 3 ≤ E ≤ N*N)

The next E lines of input contain 3 integers V₁, V₂ and C (0 ≤ C ≤ 10,000,000) each. V₁ and V₂ are the endpoints of a possible bridge that can be built, and C is the cost to build such a bridge. It is guaranteed that every pair of V₁ and V₂ only appears once.

Output

The first line of output contains one integer T, the minimum total cost to build bridges to connect all four of the largest islands together.

Sample Input

7 8
1 2 7
1 3 10
1 5 2
5 6 1
6 7 1
7 4 1
4 5 5
3 5 9

Sample Output

21