The average distance#1670
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.
The average length is defined as the sum of the lengths of shortest paths l_{a, b} for all pairs of cities , divided by the number of such pairs. Here, and are different natural numbers from to , where is the total number of cities in the country. Only consider those pairs of cities for which a shortest path exists.
The road network is provided in the input file as follows: The first line contains two numbers and (1 \leq N \leq 100, 1 \leq K \leq N(N-1)), where is the number of roads. Each of the following lines describes a one-way road: three integers a_i, b_i, and l_i (1 \leq a_i, b_i \leq N, 1 \leq l_i \leq 1000). This means there is a road of length l_i from city a_i to city b_i.
Output a single real number — the average distance between cities. The answer must be printed with digits after the decimal point.
Example 1