Ксоня и граф

Город Ксони состоит из $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\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$).

Гарантируется, что с каждого перекрестка можно добраться до каждого, пользуясь дорогами.

Гарантируется, что нет дороги с перекрестка в него же.

Гарантируется, что между двумя перекрестками не больше одной дороги.

Выходные данные

Выведите наибольшее значение $dist(u,v)$ по всем парам перекрестков $u,v$.

Примеры

Примечание

Комментарий к первому примеру.

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

Оценивание

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

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

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

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

5. ($28$ балів): без дополнительных ограничений.