Вам дано описание дорожной сети страны. Ваша задача найти среднюю длину кратчайшего пути между двумя городами.
Средней длиной называется отношение суммы по всем парам городов (a, b) длин кратчайших путей l_a_{, b} из города a в город b к числу таких пар. Здесь a и b - различные натуральные числа в диапазоне от 1 до N, где N - общее число городов в стране. Следует учитывать только такие пары городов, между которыми есть кратчайший путь.
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1 ≤ N ≤ 100, 1 ≤ K ≤ N(N − 1)), где K - количество дорог. Каждая из следующих K строк содержит описание дороги с односторонним движением - три целых числа a_i, b_i и l_i (1 ≤ a_i, b_i ≤ N, 1 ≤ l_i ≤ 1000). Это означает, что имеется дорога длины l_i, которая ведет из города a_i в город b_i.
Вы должны вывести в выходной файл единственное вещественное число среднее расстояние между городами. Расстояние должно быть выведено с 6 знаками после десятичной точки.