Yollar

Ölkə **X**-də **n** şəhər mövcuddur və bu şəhərlər **1**-dən **n**-ə qədər nömrələnmişdir. Yol şəbəkəsi **n** - **1** ikitərəfli adi yoldan ibarətdir, hər biri iki şəhəri birləşdirir və sabit uzunluğa malikdir - natural ədəd. Bu yollar müxtəlif vaxtlarda tikilmişdir və yol şəbəkəsi elə qurulmuşdur ki, istənilən iki şəhər arasında ya birbaşa, ya da digər şəhərlərdən keçməklə adi yollarla əlaqə mümkündür. Artan avtomobil hərəkəti səbəbindən hökumət bu adi yolları ikitərəfli avtomagistrallarla əvəz etməyi planlaşdırır. Avtomagistrallar aşağıdakı qaydalara uyğun olaraq tikiləcək:

- Avtomagistral yalnız artıq birbaşa yol olan iki şəhər arasında tikiləcək və bu avtomagistral həmin adi yolu əvəz edəcək.

- Eyni anda yalnız bir avtomagistral tikilə bilər;

- Avtomagistrallar adi yolların tikildiyi ardıcıllıqla tikiləcək (unutmayın ki, bütün adi yollar müxtəlif vaxtlarda tikilmişdir);

Ölkənin "rayonu" dedikdə, başlanğıc yol şəbəkəsindəki şəhərlər və adi yolların (avtomagistrallar olmadan) istənilən maksimum alt çoxluğu nəzərdə tutulur ki, oradakı istənilən iki şəhər arasında yalnız adi yollarla marşrut mövcuddur. Hər bir avtomagistral tikildikdən sonra ölkənin bir rayonu dəqiq olaraq iki rayona bölünür (ola bilər ki, yeni rayonlardan biri və ya hər ikisi yolsuz bir şəhərdən ibarət olsun). "Sadə marşrut" bir şəhərdən bir dəfədən çox keçə bilməyən marşrutdur. Hər yeni avtomagistral tikildikdən sonra **X** şəhərinin hökuməti hər iki yeni rayonda iki şəhər arasında ən uzun sadə marşrutların uzunluğunu bilmək istəyir.

Bu suallara cavab verən proqram yazın.

#### Giriş məlumatları
Birinci sətir ölkə **X**-dəki şəhərlərin sayı olan bir natural ədəd **n** (**1** ≤ **n** ≤ **500000**) ehtiva edir.

Növbəti **n** - **1** sətir avtomagistrallar tikilməzdən əvvəl mövcud olan yol şəbəkəsini təsvir edir. Hər sətir üç natural ədəd ehtiva edir - ilk ikisi adi yol olan şəhərlərin nömrələrini, üçüncüsü isə onun uzunluğunu göstərir.

Adi yollar tikildikləri ardıcıllıqla verilir.

Bütün adi yolların uzunluqları **1** və **1000** arasında daxilidir.

#### Çıxış məlumatları
**n** - **1** sətir çıxarın - **i**-ci sətirdə iki tam ədəd çıxarın, boşluqla ayrılmış - **i**-ci avtomagistral tikildikdən sonra yaranan iki yeni rayonda iki şəhər arasında ən uzun yolların uzunluqları (yalnız adi yolları istifadə edərək). Ədədləri azalan ardıcıllıqla çıxarın.

#### İzah
`t[1]`, `t[2]`, ..., `t[k]` ilə şəhərləri `t[1]`, `t[2]`, ..., `t[k]` və aralarındakı adi yolları ehtiva edən rayonu qeyd edək.

1. İlk avtomagistral tikilməzdən əvvəl:

![prb8586.gif](https://static.e-olymp.com/content/e0/e0b468fdb3692a882766465234bceed7dc961cd1.gif)

Yalnız bir rayon mövcuddur {**1**, **2**, **3**, **4**, **5**}.

2. **1** və **2** şəhərləri arasında ilk avtomagistral tikildikdən sonra:

![prb8586_1.gif](https://static.e-olymp.com/content/a6/a6abc0ff1f3317582bbbf309735f92a3b70c323e.gif)

Ölkə iki rayona bölünür - {**1**, **5**} və {**2**, **3**, **4**}. Onların hər birində şəhərlər arasında ən uzun yolların uzunluqları: {**1**, **5**} - **3** (şəhərlər **1** və **5** arasında); {**2**, **3**, **4**} - **3** (şəhərlər **3** və **4** arasında).

3. **2** və **3** şəhərləri arasında ikinci avtomagistral tikildikdən sonra:

![prb8586_2.gif](https://static.e-olymp.com/content/ff/ff161c68dc740488df3679294608f1b28a73fa7b.gif)

{**2**, **3**, **4**} rayonu iki yerə bölünür - {**3**} və {**2**, **4**}. Onların hər birində şəhərlər arasında ən uzun yolların uzunluqları **0** və **2**. Onları azalan ardıcıllıqla çıxarın!

4. **2** və **4** şəhərləri arasında üçüncü avtomagistral tikildikdən sonra:

![prb8586_3.gif](https://static.e-olymp.com/content/12/12a0a0b5221e0d401486c0d9f5efa045cba622aa.gif)

{**2**, **4**} rayonu iki yerə bölünür - {**2**} və {**4**}. Hər iki rayonda ən uzun yolların uzunluqları **0**.

5. **1** və **5** şəhərləri arasında dördüncü avtomagistral tikildikdən sonra:

![prb8586_4.gif](https://static.e-olymp.com/content/a1/a1fcfebcee32890c9c0bcb2b23e89286654dbeb1.gif)

{**1**, **5**} rayonu {**1**} və {**5**} olaraq bölünür. Ən uzun yolların uzunluqları **0**.