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.
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.
Írja ki a $$$dist(u, v)$$$ legnagyobb értékét az összes $$$u, v$$$ kereszteződés párra.
4 0 1 2 1 1 3 2 2 3 3 2 4 3
6
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$$$.