Cheapest Closed Route

Byteasar is planning an excursion through Byteland. Some pairs of cities are joined by two-way bus connections. Byteasar wants a trip that starts and ends in the same city and never uses the same bus connection twice: once he has ridden the connection between two cities in either direction, he will not ride that connection again. The fare of such a closed route is the sum of the fares of the connections it uses.

Among all non-empty closed routes that use no bus connection more than once, find the smallest possible total fare, or report that no such route exists.

The first line contains two integers $n$ and $m$ separated by a single space ($1 \le n \le 500$, $0 \le m \le 50000$): the number of cities and the number of two-way bus connections.

Each of the next $m$ lines contains three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$, $1 \le c_i \le 100000$): a connection between cities $x_i$ and $y_i$ with fare $c_i$. Each pair of cities is joined by at most one connection.

Print a single line with the minimum possible total fare of a non-empty closed route that uses no bus connection more than once. If no such route exists, print BRAK instead.