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