Вам задано опис дорожньої мережі країни. Ваша задача знайти середню довжину найкорошого шляху між двома містами. Середньою довжиною називається відношення суми по усім парам міст (\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} знаками після десяткової крапки.