Середня відстань#1670
Вам надано опис дорожньої мережі країни. Ваше завдання — знайти середню довжину найкоротшого шляху між двома містами.
Середня довжина визначається як сума довжин найкоротших шляхів l_{a, b} для всіх пар міст , поділена на кількість таких пар. Тут і — різні натуральні числа від до , де — загальна кількість міст у країні. Розглядайте лише ті пари міст, для яких існує найкоротший шлях.
Дорожня мережа подається у вхідному файлі так: у першому рядку містяться два числа і (1 \leq N \leq 100, 1 \leq K \leq N(N-1)), де — кількість доріг. Кожен з наступних рядків описує односторонню дорогу — три цілих числа a_i, b_i та l_i (1 \leq a_i, b_i \leq N, 1 \leq l_i \leq 1000). Це означає, що існує дорога довжиною l_i від міста a_i до міста b_i.
Виведіть одне дійсне число — середню відстань між містами. Відповідь повинна містити знаків після десяткової крапки.
Приклад 1