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 ai with the intersection bi and has length ci.
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.
The first line contains two integers n and g (3≤n≤200000, 0≤g≤5) — the number of intersections in the city and the group number respectively.
Each of the next n lines contains three integers ai,bi,ci (1≤ai,bi≤n, 1≤ci≤109).
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.
Print the largest value of dist(u,v) over all pairs of intersections u,v.
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.
(22 points): graph has the form of one cycle.
(17 points): n≤200.
(24 points): the length of each cycle in the graph is no more than 1000.
(9 points): ci=1.
(28 points): no additional restrictions.