Cheapest Closed Route

Time limit1sMemory limit128 MB

Summary

Given an undirected weighted graph, find the minimum total weight of a non-empty closed walk that never repeats an edge, or report none exists.

Level: Medium7 of 10
Topics: Graph, Shortest path, Greedy, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3 3
1 2 7
2 3 8
1 3 9
```
Expected output
```
24
```
Example 3
Input
```
4 3
1 2 3
2 3 4
3 4 5
```
Expected output
```
BRAK
```