Fitil

Gözəl günəşli bir gündə Kirpi sevimli çəmənliyində gəzir. Birdən, orada əvvəllər heç rast gəlmədiyi bir şeyi gördü. Uzaqdan baxanda dolaşıq ip yumağına bənzəyirdi. Yaxınlaşanda, onu açıb materialını araşdıranda, Kirpi başa düşdü ki, bu partlayıcı ipdir.

Diqqətlə baxdıqda məlum oldu ki, bunu düzəldən adamın çox boş vaxtı olub, çünki ip dolaşıq və saysız-hesabsız düyünlərlə bağlanmışdı! Dəqiq sayandan sonra müəyyən edildi ki, $n$ düyün və aralarında $m$ bağlantı var. Hər bir bağlantı iki düyünü birləşdirir və bərabər sürətlə yanır. Hər hansı bir düyün alovlandıqda, ona birləşdirilmiş bütün bağlantılar yanmağa başlayır.

Lakin Kirpinin bu tapıntısı xoşuna gəlmədi və o, onu məhv etmək qərarına gəldi. Bunun üçün, cibində təsadüfən olan kibritdən istifadə etdi. İstənilən düyünü alovlandıra bilər, bundan sonra bütün quruluş yanmağa başlayacaq. Kirpi məşğul smaşariki olduğuna görə istəyir ki, bu quruluş mümkün qədər tez yansın. Ona kömək et və hansı düyünü alovlandırmalı olduğunu təyin et.

Giriş

Birinci sətirdə $n$ və $m$ tam ədədləri verilir (2 \le n \le 100, 1 \le m \le n \cdot (n - 1) / 2) — düyünlərin sayı və onların arasındakı partlayıcı ipələrin sayı.

Növbəti $m$ sətrin hər birində üç tam ədəd - $a[i]$, $b[i]$ və $t[i]$ (1 \le a[i], b[i] \le n, a[i] \ne b[i], 1 \le t[i] \le 1000) — $i$-ci partlayıcı ipin birləşdirdiyi düyünlərin nömrələri və bu ipin hər iki ucundan yanaraq tamamilə yanma müddəti.

Hər bir düyün cütü biri-biri ilə ən çox bir partlayıcı ip vasitəsilə birləşdirilib. Zəmanət verilir ki, istənilən düyün alovlandırıldıqda bütün konstruksiyanı tamamilə yandırmaq mümkündür.

Çıxış

İki ədəd çap edin: alovlandırılmalı olan düyünün nömrəsi və bütün quruluşun tamamilə yanması üçün lazım olan vaxt.