All Roads Lead to Rome

A city is represented as a set of locations (nodes) connected by road segments (edges). A friend of mine drives around town in an unusual way that, he claims, cuts down the number of routes he has to memorize. First he picks two distinct locations to serve as hubs, $H_1$ and $H_2$. He then assigns every other location to either $H_1$ or $H_2$, and memorizes only the shortest path from each location to its assigned hub, plus the shortest path between the two hubs. (Each hub is considered assigned to itself.)

When he travels from location $A$ to location $B$, the length of his route is defined as follows. Let $h(v)$ be the hub that location $v$ is assigned to, and let $\mathrm{sp}(x, y)$ be the shortest distance between $x$ and $y$ in the road network.

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

In other words, he always visits his own hub first; if the destination's hub is different, he travels to that hub and then to the destination.

You may choose the two hubs and the assignment of the remaining locations freely. Minimize the total route length summed over every ordered pair of distinct locations $(A, B)$. (Because the number of locations is fixed, minimizing this total is the same as minimizing the average trip distance.) Output that minimum total.

The first line of input contains the number of test cases $T$.

Each test case begins with a line containing two integers $n$ and $m$ ($2 \le n \le 50$, $1 \le m \le 1000$), where $n$ is the number of locations and $m$ is the number of road segments directly connecting two locations. There may be more than one road segment between a pair of locations, and a road segment may start and end at the same location.

Each of the next $m$ lines contains three integers $a$, $b$, and $d$ ($1 \le a \le n$, $1 \le b \le n$, $1 \le d \le 1000$), meaning the road segment between locations $a$ and $b$ has length $d$. Every road is bidirectional.

A path along the road segments always exists between any two locations.

For each test case, output a single line with one integer: the minimum possible total route length summed over every ordered pair of distinct locations $(A, B)$, minimized over all choices of the two hubs and all assignments of the remaining locations to a hub.