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 ≤ *E*
≤ *N***N*)

The next *E* lines of input contain 3 integers *V*_{1}, *V*_{2} and *C* (0 ≤ *C* ≤ 10,000,000)
each.
*V*_{1} and
*V*_{2} 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*_{1} and *V*_{2} 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.

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

21

Subtask | Score |
---|---|

1 | 100 |

2 | 0 |