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


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

The next E lines of input contain 3 integers V1, V2 and C (0 ≤ C ≤ 10,000,000) each. V1 and V2 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 V1 and V2 only appears once.


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


Submitting to 'penguinislands'

You're not logged in! Click here to login

Submitting to 'penguinislands'

You're not logged in! Click here to login

Submitting .cpp to 'penguinislands'

You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 42
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0