The Xonya's city consists of $n$ crossroads connected by $n$ two-way roads. The crossroads are numbered from $1$ to $n$. The roads are also numbered from $1$ to $n$. The $i$-th road connects the intersection $a_i$ with the intersection $b_i$ and has length $c_i$. It is known that from each intersection it is possible to get to each other using roads. There is at most one road between every two intersections. There is no road leading from the intersection to it. Let's the distance $dist(x, y)$ be the length of the shortest path between the intersections $x$ and $y$. Xonya wants to find two intersections $u, v$ in the city such that $dist(u,v)$ is maximum among all possible $u, v$. \InputFile The first line contains two integers $n$ and $g$ ($3 \leq n \leq 200\,000$, $0 \leq g \leq 5$) --- the number of intersections in the city and the group number respectively. Each of the next $n$ lines contains three integers $a_i, b_i, c_i$ ($1 \leq a_i, b_i \leq n$, $1 \leq c_i \leq 10^9$). It is guaranteed that from each intersection you can get to each other using roads. It is guaranteed that there is no road from the intersection to it. It is guaranteed that there is at most one road between two intersections. \OutputFile Print the largest value of $dist(u, v)$ over all pairs of intersections $u, v$. \Note Notes to the first sample. $dist(1, 2) = 1$ $dist(1, 3) = 2$ $dist(1, 4) = 4$ $dist(2, 3) = 3$ $dist(2, 4) = 3$ $dist(3, 4) = 6$ So, the maximum is $dist(u, v) = 6$. \Scoring \begin{enumerate} \item ($22$ points): graph has the form of one cycle. \item ($17$ points): $n \leq 200$. \item ($24$ points): the length of each cycle in the graph is no more than 1000. \item ($9$ points): $c_i = 1$. \item ($28$ points): no additional restrictions. \end{enumerate}