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