Задача Среднее расстояние

Описание

Вам дано описание дорожной сети страны. Ваша задача – найти среднюю длину кратчайшего пути между двумя городами. Средней длиной называется отношение суммы по всем парам городов (a, b) длин кратчайших путей la,b из города a в город b к числу таких пар. Здесь a и b – различные натуральные числа в диапазоне от 1 до N, где N – общее число городов в стране. Следует учитывать только такие пары городов, между которыми есть кратчайший путь.

Формат входных данных

Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1 <= N <= 100, 1 <= K <= N(N − 1)), где K – количество дорог. Каждая из следующих K строк содержит описание дороги с односторонним движением _ три целых числа ai, bi и li (1 <= ai, bi <= N, 1 <= li <= 1 000). Это означает, что имеется дорога длины li, которая ведет из города ai в город bi.

Формат выходных данных

Вы должны вывести в выходной файл единственное вещественное число – среднее расстояние между городами. Расстояние должно быть выведено с 6 знаками после десятичной точки.