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