가장 저렴한 순환 여행

바이트랜드를 여행하려는 바이트아사르가 있다. 어떤 두 도시들은 양방향 버스 노선으로 이어져 있다. 바이트아사르는 한 도시에서 출발해 같은 도시로 돌아오는 여행을 하되, 같은 버스 노선을 두 번 이상 타지 않으려 한다. 즉 두 도시를 잇는 노선을 어느 방향으로든 한 번 타고 나면 그 노선은 다시 타지 않는다. 이렇게 만든 닫힌 경로의 요금은 사용한 노선들의 요금을 모두 더한 값이다.

같은 노선을 두 번 이상 쓰지 않는, 비어 있지 않은 모든 닫힌 경로 중에서 요금 합이 가장 작은 값을 구하여라. 그런 경로가 하나도 없으면 없다고 답한다.

첫째 줄에 도시의 수 $n$과 양방향 버스 노선의 수 $m$이 공백으로 구분되어 주어진다 ($1 \le n \le 500$, $0 \le m \le 50000$).

다음 $m$개의 줄에는 각각 세 정수 $x_i$, $y_i$, $c_i$가 주어진다 ($1 \le x_i, y_i \le n$, $x_i \ne y_i$, $1 \le c_i \le 100000$). 이는 도시 $x_i$와 $y_i$를 잇는 요금 $c_i$의 노선을 뜻한다. 어떤 두 도시 사이에도 노선은 최대 한 개만 있다.

같은 노선을 두 번 이상 쓰지 않는, 비어 있지 않은 닫힌 경로의 최소 요금 합을 한 줄에 출력한다. 그런 경로가 존재하지 않으면 대신 BRAK을 출력한다.