투르 드 프랑스

투르 드 프랑스 조직위원회는 선정한 프랑스 도시를 모두 지나는 가장 짧은 경로를 원한다. 이 경로는 순회 경로여야 한다. 한 도시에서 출발해 나머지 도시를 각각 정확히 한 번씩 방문하고 출발한 도시로 돌아오며, 각 구간은 앞 구간이 끝난 도시에서 시작한다.

임의의 도로망에서 최단 순회 경로를 찾는 문제는 외판원 문제이고, 계획한 구간 수는 그 방법으로 감당하기에 너무 많다. 그래서 조직위원회가 조건을 하나 걸었다. 각 도시는 목적지 후보로 다른 도시를 최대 두 곳만 내놓고, 각 도시는 최대 두 도시에서 들어오는 경로만 받아 준다. 그래프로 옮기면 도로망은 모든 정점의 나가는 차수가 $2$ 이하이고 들어오는 차수도 $2$ 이하인 방향 그래프다.

도로는 일방통행이다. 도시 $a$에서 도시 $b$로 가는 도로가 있다고 해서 반대 방향 도로가 있는 것은 아니고, 양쪽 다 있더라도 길이는 서로 다를 수 있다.

이런 그래프가 주어질 때 모든 도시를 정확히 한 번씩 지나 출발 도시로 돌아오는 가장 짧은 순회 경로의 길이를 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 50$). 각 테스트 케이스는 다음과 같은 형식이다.

• 첫 줄에 도시의 수 $N$과 도로의 수 $M$이 공백으로 구분되어 주어진다 ($3 \le N \le 36$, $N \le M \le 2N$).
• 이어지는 $M$개 줄에 세 정수 $i$, $j$, $d$가 공백으로 구분되어 주어진다 ($0 \le i, j < N$, $i \ne j$, $1 \le d \le 10000$). 도시 $i$에서 도시 $j$로 가는 길이 $d$짜리 일방통행 도로가 있다는 뜻이다.

같은 순서쌍 $(a, b)$에 대한 도로는 최대 한 번만 주어지지만, 반대 방향인 $b$에서 $a$로 가는 도로가 다른 길이로 함께 주어지기도 한다. 한 도시에서 나가는 도로는 최대 두 개이고, 한 도시로 들어오는 도로도 최대 두 개다. 모든 테스트 케이스에는 순회 경로가 적어도 하나 존재한다.

각 테스트 케이스마다 $N$개 도시를 모두 지나는 최단 순회 경로의 길이를 한 줄에 출력한다.