0127. Average Length

Input file name:	average.in
Output file name:	average.out
Time limit:	500 ms
Memory limit:	64 megabytes

You are given a description of a working road network. Your task is to find average length of the shortest path between two towns in this network.

The average length is a sum (for all the pairs (a, b) where the shortest path exists from a to b and has length l_i) of all the l_i, divided by a number of such pairs. a and b in this definition are different integer numbers less or equal to n – the total number of towns.

Input file

The first two numbers in the input are n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ n(n-1)). The next k lines contain three integers each (a_i b_i L_i, 1 ≤ a_i, b_i ≤ n, 1 ≤ L_i ≤ 1000) representing a one-way road from a_i to b_i of length L_i.

Output file

You are to display only one number rounded to 6 digits after decimal point – average length of the shortest path.

Examples:

average.in	average.out
6 4 1 2 7 3 4 8 4 5 1 4 3 100	25.000000

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version