Ксоня та граф#11070
Місто Ксоні складається з перехресть, з'єднаних між собою двосторонніми дорогами.
Перехрестя пронумеровані від до . Дороги також пронумеровані від до . -та дорога з'єднує перехрестя з номером a_i з перехрестям з номером b_i і має довжину c_i.
Відомо, що від кожного перехрестя можна добратися до кожного іншого, використовуючи наявні дороги. Між кожними двома перехрестями є не більше однієї дороги. Немає дороги, яка веде з перехрестя в нього ж.
Назвемо відстанню dist(x, y) довжину найкоротшого шляху між перехрестями і .
Ксоня хоче знайти два перехрестя в місті, такі, що dist(u,v) — максимальний серед усіх можливих .
Перший рядок містить два цілі числа і (3 \leq n \leq 200\,000, 0 \leq g \leq 5) — кількість перехресть у місті та номер групи відповідно.
Кожен з наступних рядків містить по три цілі числа a_i, b_i, c_i (1 \leq a_i, b_i \leq n, 1 \leq c_i \leq 10^9).
Гарантується, що з кожного перехрестя можна дістатися до кожного іншого, користуючись дорогами.
Гарантується, що немає дороги, що веде з перехрестя в нього ж.
Гарантується, що між двома перехрестями не більше однієї дороги.
Виведіть найбільше значення dist(u, v) по усім парам перехресть .
Приклад 1
Коментар до першого приклада.
dist(1, 2) = 1
dist(1, 3) = 2
dist(1, 4) = 4
dist(2, 3) = 3
dist(2, 4) = 3
dist(3, 4) = 6
Отже, максимальний dist(u, v) = 6.
( бали): граф має вигляд одного циклу.
( балів): n \leq 200.
( бали): довжина кожного циклу в графі не більше .
( балів): c_i = 1.
( балів): без додаткових обмежень.