Ксоня və qraf

Məkan Ksoni $n$ kəsişmədən ibarətdir və bu kəsişmələr $n$ ikitərəfli yollarla birləşdirilib.

Kəsişmələr $1$-dən $n$-ə qədər nömrələnib. Yollar da $1$-dən $n$-ə qədər nömrələnib. $i$-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 $x$ və $y$ 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ə $u,v$ tapmaq istəyir ki, $dist(u,v)$ bütün mümkün $u,v$ arasında maksimal olsun.

Giriş verilənləri

Birinci sətir şəhərdəki kəsişmələrin sayı və qrup nömrəsi olan iki tam ədəd $n$ və $g$ ($3\le n\le 200000$, $0\le g\le 5$) ehtiva edir.

Növbəti $n$ sətirin hər biri üç tam ədəd $a_i,b_i,c_i$ ($1\le a_i,b_i\le n$, $1\le c_i\le 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.

Çıxış verilənləri

Bütün kəsişmə cütləri $u,v$ üçün ən böyük $dist(u,v)$ dəyərini çıxarın.

Nümunələr

Qeyd

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$.

Qiymətləndirmə

1. ($22$ xal): qraf bir dövrə şəklindədir.

2. ($17$ xal): $n\le 200$.

3. ($24$ xal): qrafdakı hər bir dövrənin uzunluğu 1000-dən çox deyil.

4. ($9$ xal): $c_i=1$.

5. ($28$ xal): əlavə məhdudiyyətlər olmadan.