Среднее расстояние
Вам дано описание дорожной сети страны. Ваша задача – найти среднюю длину кратчайшего пути между двумя городами. Средней длиной называется отношение суммы по всем парам городов ($a$, $b$) длин кратчайших путей $l_{a,b}$ из города $a$ в город $b$ к числу таких пар. Здесь $a$ и $b$ – различные натуральные числа в диапазоне от 1 до $N$, где $N$ – общее число городов в стране. Следует учитывать только такие пары городов, между которыми есть кратчайший путь.
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа $N$ и $K$ ($1 \leq N \leq 100, 1 \leq K \leq N(N-1)$), где $K$ – количество дорог. Каждая из следующих $K$ строк содержит описание дороги с односторонним движением – три целых числа $a_i$, $b_i$ и $l_i$ ($1 \leq a_i,b_i \leq N$, $1 \leq l_i \leq 1000$). Это означает, что имеется дорога длины $l_i$, которая ведет из города $a_i$ в город $b_i$.
Вы должны вывести в выходной файл единственное вещественное число – среднее расстояние между городами. Расстояние должно быть выведено с 6 знаками после десятичной точки.
6 4 1 2 7 3 4 8 4 5 1 4 3 100
25.000000