순찰 경로

Ahmad shah는 카불의 순찰관이다. 매일 밤 그는 여러 경찰서를 잇는 거대한 오솔길 네트워크를 받아 밤사이 그 사이를 순찰해야 한다. Ahmad shah는 모든 오솔길을 적어도 한 번씩 지나는 가장 짧은 경로를 찾고자 한다. 그를 도와 그 경로를 찾아라.

각 테스트 케이스의 입력 첫 줄에는 두 양의 정수 $n \le 15$와 $m < 1000$이 주어진다. $n$은 경찰서의 수, $m$은 오솔길의 수이다. 각 오솔길마다 한 줄이 이어지며, 세 양의 정수가 주어진다. 처음 두 정수는 1과 $n$ 사이의 값으로 오솔길 양 끝의 경찰서를 나타내고, 세 번째 정수는 그 오솔길의 길이를 나타낸다. 두 경찰서 사이에 오솔길이 여러 개 있을 수 있다. 서로 다른 오솔길은 입력에 한 번씩만 주어진다. 각 오솔길은 양방향으로 지날 수 있다. 오솔길로 연결된 경찰서를 순서대로 지나가면 어떤 오솔길에서든 다른 오솔길로 갈 수 있다. Ahmad shah의 경로는 어느 경찰서에서든 시작할 수 있지만, 시작한 경찰서와 같은 곳에서 끝나야 한다. 마지막 테스트 케이스 뒤에는 0 하나만 있는 줄이 온다.

각 테스트 케이스마다 Ahmad shah의 경로 길이를 한 줄에 출력한다.