Ксоня та граф
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Місто Ксоні складається з $$$n$$$ перехресть, з'єднаних між собою $$$n$$$ двосторонніми дорогами.

Перехрестя пронумеровані від $$$1$$$ до $$$n$$$. Дороги також пронумеровані від $$$1$$$ до $$$n$$$. $$$i$$$-та дорога з'єднує перехрестя з номером $$$a_i$$$ з перехрестям з номером $$$b_i$$$ і має довжину $$$c_i$$$.

Відомо, що від кожного перехрестя можна добратися до кожного іншого, використовуючи наявні дороги. Між кожними двома перехрестями є не більше однієї дороги. Немає дороги, яка веде з перехрестя в нього ж.

Назвемо відстанню $$$dist(x, y)$$$ довжину найкоротшого шляху між перехрестями $$$x$$$ і $$$y$$$.

Ксоня хоче знайти два перехрестя $$$u, v$$$ в місті, такі, що $$$dist(u,v)$$$ — максимальний серед усіх можливих $$$u,v$$$.

Вхідні дані

Перший рядок містить два цілі числа $$$n$$$ і $$$g$$$ ($$$3 \leq n \leq 200\,000$$$, $$$0 \leq g \leq 5$$$) — кількість перехресть у місті та номер групи відповідно.

Кожен з наступних $$$n$$$ рядків містить по три цілі числа $$$a_i, b_i, c_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$1 \leq c_i \leq 10^9$$$).

Гарантується, що з кожного перехрестя можна дістатися до кожного, користуючись дорогами.

Гарантується, що немає дороги з перехрестя в себе.

Гарантується, що між двома перехрестями не більше однієї дороги.

Вихідні дані

Виведіть найбільше значення $$$dist(u, v)$$$ по усім парам перехресть $$$u, v$$$.

Система оцінки

  1. ($$$22$$$ бали): граф має вигляд одного циклу.
  2. ($$$17$$$ балів): $$$n \leq 200$$$.
  3. ($$$24$$$ бали): довжина кожного циклу в графі не більше 1000.
  4. ($$$9$$$ балів): $$$c_i = 1$$$.
  5. ($$$28$$$ балів): без додаткових обмежень.

Приклад

Вхідні дані
4 0
1 2 1
1 3 2
2 3 3
2 4 3
Вихідні дані
6

Пояснення

Коментар до першого приклада.

$$$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$$$.