Город Ксони состоит из $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$. \InputFile Первая строка содержит два целых числа $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$). Гарантируется, что с каждого перекрестка можно добраться до каждого, пользуясь дорогами. Гарантируется, что нет дороги с перекрестка в него же. Гарантируется, что между двумя перекрестками не больше одной дороги. \OutputFile Выведите наибольшее значение $dist(u, v)$ по всем парам перекрестков $u, v$. \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 \begin{enumerate} \item ($22$ бали): граф имеет вид одного цикла. \item ($17$ балів): $n \leq 200$. \item ($24$ бали): длина каждого цикла в графе не больше 1000. \item ($9$ балів): $c_i = 1$. \item ($28$ балів): без дополнительных ограничений. \end{enumerate}