Xonia és a gráf
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Xonia városa $$$n$$$ kereszteződésekből áll, amelyeket $$$n$$$ kétirányú utak kötnek össze.

A kereszteződések $$$1$$$-től $$$n$$$-ig vannak számozva. Az utak is $$$1$$$-től $$$n$$$-ig vannak számozva. Az $$$i$$$–edik út az $$$a_i$$$ számú kereszteződést köti össze a $$$b_i$$$ számú kereszteződéssel, és hossza $$$c_i$$$.

Ismeretes, hogy minden kereszteződésből mindegyikhez a meglévő utakon lehet eljutni. A két kereszteződés között legfeljebb egy út van. A kereszteződésből nem vezet oda út.

Nevezzük a távolságot $$$dist(x, y)$$$ az $$$x$$$ és $$$y$$$ kereszteződések közötti legrövidebb út hosszának.

Xonia két $$$u, v$$$. kereszteződést akar találni a városban, úgy, hogy $$$dist(u,v)$$$ — a maximum az összes lehetséges $$$u,v$$$. között.

Input

Az első sor két egész számot tartalmaz: $$$n$$$ és $$$g$$$ ($$$3 \leq n \leq 200\,000$$$, $$$0 \leq g \leq 5$$$) — a kereszteződések száma a városban és a csoportban száma.

A következő $$$n$$$ sorok mindegyike három egész számot tartalmaz: $$$a_i, b_i, c_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$1 \leq c_i \leq 10^9$$$).

Garantáltan minden kereszteződésből mindenkit elérhet az utakon.

Garantált, hogy a kereszteződésből önmagába nincs út.

Garantált, hogy két kereszteződés között nincs több, mint egy út.

Output

Írja ki a $$$dist(u, v)$$$ legnagyobb értékét az összes $$$u, v$$$ kereszteződés párra.

Scoring

  1. ($$$22$$$ pont): a gráf egy ciklus alakú.
  2. ($$$17$$$ pont): $$$n \leq 200$$$.
  3. ($$$24$$$ pont): az oszlopban az egyes ciklusok hossza nem haladja meg az 1000-et.
  4. ($$$9$$$ pont): $$$c_i = 1$$$.
  5. ($$$28$$$ pont): további korlátozások nélkül.

Example

Input
4 0
1 2 1
1 3 2
2 3 3
2 4 3
Output
6

Note

Megjegyzés az első példához.

$$$dist(1, 2) = 1$$$

$$$dist(1, 3) = 2$$$

$$$dist(1, 4) = 4$$$

$$$dist(2, 3) = 3$$$

$$$dist(2, 4) = 3$$$

$$$dist(3, 4) = 6$$$

Szóval a maximum $$$dist(u, v) = 6$$$.