농장과 공장

바이트랜드의 국왕 비톨로뮤 만세!

비톨로뮤 국왕이 다스리는 바이트랜드는 작은 나라이다. 국왕을 제외한 모든 국민은 서로 다른 두 도시에 위치한 농장 또는 공장 중 한 곳에서 일한다. 그래서 매일 아침 각 도시의 주민들은 이 두 도시로 출근한다.

바이트랜드의 도로망은 서로 다른 두 도시를 잇는 무방향 도로들로 이루어져 있다. 도로는 도시에서만 만나며(다리와 터널은 허용된다), 같은 두 도시를 직접 잇는 도로가 여러 개 있을 수도 있다. 농장과 공장은 모든 도시에서 도달할 수 있다.

얼마 전 국왕은 모든 도로에 고정 통행료를 매겼다. 국민이 어떤 도로를 지날 때마다 그 도로의 통행료를 내야 한다. 그 뒤로 모든 국민은 통행료의 합이 최소가 되는 가장 저렴한 경로로 출근한다.

이제 국왕은 도시 하나를 새로 만들어 새 수도로 삼으려 한다. 새 수도는 기존 도시들 중 일부와 새 도로로 직접 연결되어, 모든 도시에 새 수도에서 도달할 수 있어야 한다. 새로 놓는 각 도로에는 임의의 음이 아닌 통행료(정수가 아니어도 된다)를 매길 수 있다.

국왕은 새 도로들의 통행료를, 수도가 아닌 모든 도시 $v$에 대해 $v$에서 농장까지의 가장 저렴한 경로와 $v$에서 공장까지의 가장 저렴한 경로가 각각 존재하되 그 두 경로 모두 수도를 지나지 않도록 정하려 한다(여기서 $v$는 농장이나 공장 도시일 수도 있다). 이 조건을 만족시키면서, 수도에서 각 도시까지의 가장 저렴한 경로 비용을 $n$개의 모든 도시에 대해 평균한 값을 최소화하려 한다.

이 최소 평균 비용을 구하여 국왕을 도와라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$, $m$ ($2 \le n \le 10^5$, $1 \le m \le 3\cdot10^5$)이 주어진다. 각각 도시의 수와 도로의 수이다. 이어지는 $m$개의 줄에는 각각 세 정수 $u$, $v$, $c$ ($1 \le u, v \le n$, $u \ne v$, $0 \le c \le 10^6$)가 주어지며, 이는 도시 $u$와 $v$를 잇고 통행료가 $c$인 도로를 나타낸다. 같은 두 도시를 잇는 도로가 여러 개일 수 있다.

농장은 $1$번 도시, 공장은 $2$번 도시이며, 둘 다 모든 도시에서 도달할 수 있다.

각 테스트 케이스마다 최소 평균 비용을 한 줄에 출력한다.

답은 항상 유리수이다. 기약분수 p/q 형태로 출력하되 $q \ge 1$이고 $\gcd(p, q) = 1$이어야 한다(답이 정수이면 $q = 1$). 예를 들어 답이 $\tfrac{11}{6}$이면 11/6으로, 답이 $2$이면 2/1로 출력한다.