Xonya and graph

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

Input

The first line contains two integers $n$ and $g$ ($3\le n\le 200000$, $0\le g\le 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\le a_i,b_i\le n$, $1\le c_i\le 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.

Output

Print the largest value of $dist(u,v)$ over all pairs of intersections $u,v$.

Examples

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

1. ($22$ points): graph has the form of one cycle.

2. ($17$ points): $n\le 200$.

3. ($24$ points): the length of each cycle in the graph is no more than 1000.

4. ($9$ points): $c_i=1$.

5. ($28$ points): no additional restrictions.