Ксоня və qraf#11070
Məkan Ksoni kəsişmədən ibarətdir və bu kəsişmələr ikitərəfli yollarla birləşdirilib.
Kəsişmələr -dən -ə qədər nömrələnib. Yollar da -dən -ə qədər nömrələnib. -ci yol a_i nömrəli kəsişməni b_i nömrəli kəsişmə ilə birləşdirir və uzunluğu c_i-dir.
Hər bir kəsişmədən digərinə mövcud yollarla çatmaq mümkündür. Hər iki kəsişmə arasında yalnız bir yol var və özünə gedən yol yoxdur.
dist(x, y) məsafəsini və kəsişmələri arasındakı ən qısa yolun uzunluğu kimi təyin edək.
Ksoni şəhərdə elə iki kəsişmə tapmaq istəyir ki, dist(u,v) bütün mümkün arasında maksimal olsun.
Birinci sətir şəhərdəki kəsişmələrin sayı və qrup nömrəsi olan iki tam ədəd və (3 \leq n \leq 200\,000, 0 \leq g \leq 5) ehtiva edir.
Növbəti sətirin hər biri üç tam ədəd a_i, b_i, c_i (1 \leq a_i, b_i \leq n, 1 \leq c_i \leq 10^9) ehtiva edir.
Hər bir kəsişmədən digərinə yollarla çatmaq mümkün olduğu təmin edilir.
Özünə gedən yol olmadığı təmin edilir.
İki kəsişmə arasında bir yoldan çox olmadığı təmin edilir.
Bütün kəsişmə cütləri üçün ən böyük dist(u, v) dəyərini çıxarın.
Nümunə 1
Birinci nümunəyə şərh.
dist(1, 2) = 1
dist(1, 3) = 2
dist(1, 4) = 4
dist(2, 3) = 3
dist(2, 4) = 3
dist(3, 4) = 6
Beləliklə, maksimal dist(u, v) = 6.
( xal): qraf bir dövrə şəklindədir.
( xal): n \leq 200.
( xal): qrafdakı hər bir dövrənin uzunluğu 1000-dən çox deyil.
( xal): c_i = 1.
( xal): əlavə məhdudiyyətlər olmadan.