조깅 코스

고드(Gord)는 마라톤을 준비하며 훈련하고 있다. 그의 집 뒤에는 급수대(water station)들을 연결하는 여러 조깅 길(trail)로 이루어진 큰 공원이 있다. 고드는 모든 길을 적어도 한 번씩 지나는 가장 짧은 조깅 경로의 길이를 구하려고 한다. 경로는 어떤 급수대에서 출발해도 되지만, 반드시 출발한 급수대로 되돌아와야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 양의 정수 $n$과 $m$이 주어진다. $n$은 급수대의 수로 $n \le 15$이고, $m$은 길의 수로 $m < 1000$이다. 이어지는 $m$개의 줄에는 각각 세 양의 정수가 주어진다. 앞의 두 정수는 그 길의 양 끝 급수대 번호로 각각 $1$ 이상 $n$ 이하이며, 세 번째 정수는 그 길의 길이(큐빗 단위)이다. 두 급수대 사이에 길이 여러 개 있을 수 있고, 서로 다른 각 길은 입력에 한 번씩만 주어지며, 모든 길은 양방향으로 지날 수 있다. 어떤 길에서 출발하더라도 급수대들을 거쳐 다른 모든 길에 도달할 수 있다(즉, 이 그래프는 연결되어 있다). 마지막 테스트 케이스 다음에는 $0$ 하나만 있는 줄이 온다.

각 테스트 케이스마다, 고드의 가장 짧은 조깅 경로의 길이를 한 줄에 하나씩 출력한다.