Xonia és a gráf #11070
Xonia városa kereszteződésekből áll, amelyeket kétirányú utak kötnek össze.
A kereszteződések -től -ig vannak számozva. Az utak is -től -ig vannak számozva. Az –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 és kereszteződések közötti legrövidebb út hosszának.
Xonia két . kereszteződést akar találni a városban, úgy, hogy dist(u,v) — a maximum az összes lehetséges . között.
Az első sor két egész számot tartalmaz: és (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ő 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 kereszteződés párra.
1. példa
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.
( pont): a gráf egy ciklus alakú.
( pont): n \leq 200.
( pont): az oszlopban az egyes ciklusok hossza nem haladja meg az 1000-et.
( pont): c_i = 1.
( pont): további korlátozások nélkül.