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