ZOJ Problem Set - 2897
Trapped in a remote group of islands, Desmond keeps running everyday because he never gives up on the hope that he will have a strong body to win the upcoming World's Sailing Race, get a huge prize out of it, and marry his beloved girl Penny.
There are N small islands located in this area, connected by two way bridges previously built by a discontinued research project. Every island is reachable from every other via bridges. However some bridges are more important, and Desmond calls them critical bridges. More specifically, a bridge is called critical if and only if its removal results in a separation of the islands into two mutually unreachable parts. Desmond has found, after exhaustive explorations, that if all the critical bridges are removed, then the islands will be separated into several (mutually unreachable) connected parts, where each part consists of at most 20 islands.
Every day Desmond randomly picks a starting island, and runs to a randomly-chosen destination island different from the starting one. His running distance is the sum of the lengths of all bridges he crosses on his path. Desmond always uses the shortest running distance between the two chosen islands.
As a way to measure his training strength, Desmond needs to know the average distance of his daily running. He turns to you for help.
For example, there are 3 islands, connected by bridges as 1-2-3 and each bridge has a length of 1. Desmond's daily choice would be from 1 to 2, from 1 to 3, from 2 to 1, from 2 to 3, from 3 to 1, or from 3 to 2. The average running distance should be (1+2+1+1+2+1)/6 = 4/3.
The input consists of multiple test cases.
On the first line of each test case are two integers N(2<=N<=10000) and M(1<=M<=100000), the number of islands and the number of bridges connecting them. Next M lines each contain three integers A, B and C(1<=A,B<=N, 1<=C<=1000), meaning there is a two way bridge connecting islands A and B, whose length is C. You can assume that any pair of islands is connected by at most one bridge, there is no bridge connecting an island to itself, and the curious properties stated in the second paragraph always hold.
Process to the end of file.
For each case, output on a line the average distance of Desmond's daily running. Output the answer as a reduced fraction A/B.
Author: LIU, Xin
Source: ZOJ Monthly, January 2008