The average distance
You are given a description of the country's road network. Your task is to find the average length of the shortest path between two cities
Average length is the ratio of the sum over all pairs of cities (a, b) the lengths of shortest paths l_a_{, b} of the city in a city b to the number of such pairs. Here a and b - a variety of natural numbers from 1 to N, where N - total number of cities in the country. Should consider only those pairs of cities, among which is the shortest path.
Input
The road network is given in the input file as follows: The first line contains the numbers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ N(N − 1)), where K - number of roads. Each of the following K lines contains the description of one-way road - three integers a_i, b_i and l_i (1 ≤ a_i, b_i ≤ N, 1 ≤ l_i ≤ 1000). This means that there is a path of length l_i, which leads out of town a_i to the city b_i.
Output
You must bring to the output file a unique real number of the average distance between cities. Distance must be inferred from 6 characters after the decimal point.