Місто Ксоні складається з $$$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$$$.
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$$$.