Xonya and graph#11070
The Xonya's city consists of crossroads connected by two-way roads.
The crossroads are numbered from to . The roads are also numbered from to . The -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 and .
Xonya wants to find two intersections in the city such that dist(u,v) is maximum among all possible .
The first line contains two integers and (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 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.
Print the largest value of dist(u, v) over all pairs of intersections .
Example 1
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.
( points): graph has the form of one cycle.
( points): n \leq 200.
( points): the length of each cycle in the graph is no more than 1000.
( points): c_i = 1.
( points): no additional restrictions.