모든 길은 로마로 통한다

어떤 도시를 여러 개의 장소(정점)와 도로 구간(간선)으로 나타낸다. 한 친구는 외워야 하는 경로의 수를 줄이려고 독특한 방식으로 이동한다. 먼저 서로 다른 두 장소를 허브 $H_1$, $H_2$ 로 정한다. 그런 다음 나머지 모든 장소를 $H_1$ 또는 $H_2$ 중 하나에 배정하고, 각 장소에서 자신이 배정된 허브까지의 최단 경로와 두 허브 사이의 최단 경로만 외운다. (허브 자신은 자기 자신에게 배정된 것으로 본다.)

장소 $A$ 에서 장소 $B$ 로 이동할 때 친구의 경로 길이는 다음과 같이 정의한다. $h(v)$ 를 장소 $v$ 가 배정된 허브, $\mathrm{sp}(x, y)$ 를 도로망에서 $x$ 와 $y$ 사이의 최단 거리라 하자.

• $h(A) = h(B)$ 이면: $\mathrm{sp}(A, h(A)) + \mathrm{sp}(h(A), B)$
• $h(A) \ne h(B)$ 이면: $\mathrm{sp}(A, h(A)) + \mathrm{sp}(h(A), h(B)) + \mathrm{sp}(h(B), B)$

즉 친구는 언제나 자신의 허브를 먼저 들르고, 목적지의 허브가 다르면 그 허브까지 이동한 뒤 목적지로 간다.

두 허브의 선택과 나머지 장소들의 배정을 자유롭게 정할 수 있다. 서로 다른 모든 장소 순서쌍 $(A, B)$ 에 대한 친구 경로 길이의 총합을 최소로 만들어라. (장소 개수는 고정이므로 이 총합을 최소화하는 것은 모든 이동의 평균 거리를 최소화하는 것과 같다.) 그 최소 총합을 출력한다.

입력의 첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$ 과 $m$ 이 주어진다 ($2 \le n \le 50$, $1 \le m \le 1000$). $n$ 은 도시의 장소 수, $m$ 은 두 장소를 직접 잇는 도로 구간의 수이다. 한 쌍의 장소 사이에 도로 구간이 여러 개 있을 수 있고, 시작과 끝이 같은 도로 구간도 있을 수 있다.

이어지는 $m$ 개의 줄에는 각각 세 정수 $a$, $b$, $d$ 가 주어지며 ($1 \le a \le n$, $1 \le b \le n$, $1 \le d \le 1000$), 장소 $a$ 와 $b$ 를 잇는 도로 구간의 길이가 $d$ 임을 뜻한다. 모든 도로는 양방향이다.

임의의 두 장소 사이에는 항상 도로를 따라가는 경로가 존재한다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다: 서로 다른 모든 장소 순서쌍 $(A, B)$ 에 대한 친구 경로 길이 총합의 최솟값. 최솟값은 두 허브의 선택과 나머지 장소들의 허브 배정을 모두 고려하여 정한다.