Ксоня та граф

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

Input

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

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

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

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

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

Output

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

Examples

Note

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

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

Scoring

1. ($22$ бали): граф має вигляд одного циклу.

2. ($17$ балів): $n\le 200$.

3. ($24$ бали): довжина кожного циклу в графі не більше 1000.

4. ($9$ балів): $c_i=1$.

5. ($28$ балів): без додаткових обмежень.