Farm and Factory

All hail Bitolomew, the king of Byteland!

King Bitolomew rules a small country. Every citizen except the king works at either the farm or the factory, which are located in two different cities, so every morning the residents of each city commute to those two cities.

The road network of Byteland consists of undirected roads, each joining a pair of distinct cities. Roads meet only at cities (bridges and tunnels are allowed), and several roads may directly connect the same pair of cities. Both the farm and the factory are reachable from every city.

Some time ago the king put a fixed toll on every road: each time a citizen travels along a road, they must pay that road's toll. Since then, every citizen commutes along a cheapest route, i.e. one whose total toll is minimum.

The king now wants to found a brand-new capital as one additional city. The capital must be connected to some of the existing cities by new direct roads so that every city is reachable from it. Each new road may be given any non-negative toll (not necessarily an integer).

The king wants to set the tolls of the new roads so that for every city $v$ other than the capital there exists a cheapest path from $v$ to the farm and a cheapest path from $v$ to the factory, neither of which passes through the capital (here $v$ may itself be the farm or the factory). Subject to this requirement, he wants to minimize the average, over all $n$ cities, of the cost of a cheapest path from the capital to that city.

Help the king determine this minimum possible average cost.

The first line contains an integer $T$, the number of test cases. The test cases follow.

Each test case begins with a line containing two integers $n$ and $m$ ($2 \le n \le 10^5$, $1 \le m \le 3\cdot10^5$): the number of cities and the number of roads. Each of the next $m$ lines contains three integers $u$, $v$, $c$ ($1 \le u, v \le n$, $u \ne v$, $0 \le c \le 10^6$): a road between cities $u$ and $v$ with toll $c$. Several roads may connect the same pair of cities.

The farm is city $1$ and the factory is city $2$; both are reachable from every city.

For each test case, print a single line with the minimum possible average cost.

The answer is always rational; print it as an irreducible fraction p/q in lowest terms with $q \ge 1$ (so $\gcd(p, q) = 1$, and $q = 1$ when the answer is an integer). For example, an answer of $\tfrac{11}{6}$ is printed as 11/6, and an answer of $2$ is printed as 2/1.