Ксоня та граф
Місто Ксоні складається з перехресть, з'єднаних між собою двосторонніми дорогами.
Перехрестя пронумеровані від до . Дороги також пронумеровані від до . -та дорога з'єднує перехрестя з номером з перехрестям з номером і має довжину .
Відомо, що від кожного перехрестя можна добратися до кожного іншого, використовуючи наявні дороги. Між кожними двома перехрестями є не більше однієї дороги. Немає дороги, яка веде з перехрестя в нього ж.
Назвемо відстанню довжину найкоротшого шляху між перехрестями і .
Ксоня хоче знайти два перехрестя в місті, такі, що — максимальний серед усіх можливих .
Вхідні дані
Перший рядок містить два цілі числа і (, ) — кількість перехресть у місті та номер групи відповідно.
Кожен з наступних рядків містить по три цілі числа (, ).
Гарантується, що з кожного перехрестя можна дістатися до кожного, користуючись дорогами.
Гарантується, що немає дороги з перехрестя в себе.
Гарантується, що між двома перехрестями не більше однієї дороги.
Вихідні дані
Виведіть найбільше значення по усім парам перехресть .
Приклади
Примітка
Коментар до першого приклада.
Отже, максимальний .
Оцінювання
( бали): граф має вигляд одного циклу.
( балів): .
( бали): довжина кожного циклу в графі не більше 1000.
( балів): .
( балів): без додаткових обмежень.