Gözəl günəşli gündə Kirpi sevimli çəmənliyində gəzirdi. Lakin o indiyə qədər çəmənlikdə görmədiyi qeyri-adi bir şey gördü. Bu uzaqdan dolaşıq bir ipə bənzəyirdi. Lakin ona yaxınlaşıb açdı, onun hansı materialdan hazırlandığını öyrəndikdən sonra Kirpi bunun fitil olduğu qərarına gəldi.

Ona diqqətlə baxdıqdan sonra Kirpi qərara gəldi ki, görünür ki, onu kim hazırlamışdırsa, onun üçün bu darıxdırıcı idi və onun boş vaxtı yox idi, belə ki, ip qarışdırılmışdı və onda çoxlu sayda düyünlər vardı. Uzun əziyyətlə düyünləri saydıqdan sonra aydın oldu ki, n düyün və düyünlər arasında m birləşmə var. Onların hər biri iki düyünü birləşdirir və bərabər zamanda yanır. Düyünü yandırarkən onu əlaqələndirən bütün birləşmələr yanır.

Lakin, bu tapıntı Kirpinin xoşuna gəlmədi, onu məhv etmək qərarına gəldi. Bunun üçün o cibindəki kibritdən istifadə etmək qərarına gəldi. O fitilin düyünlərindən elə birini yandıra bilərdi ki, bu konstruksiya tamamilə yansın. Kirpi bu konstruksiyanın tez bir zamanda yanmasını istəyir. Bunun üçün hansı düyünü yandırmaq lazım gəldiyini müəyyənləşdirmək üçün ona kömək edin.

Giriş verilənləri

Giriş faylının ilk sətri düyünlərin və düyünlər arasındakı iplərin sayını ifadə edən iki n və m (2 ≤ n ≤ 100, 1 ≤ m ≤ n * (n - 1) / 2) tam ədədlərini ehtiva edir.

Növbəti m sətir düyünlər arasındakı əlaqələri əks etdirən üç ai, bi və ti (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ti ≤ 1000) tam ədədlərini - i-ci ipin birləşdirdiyi düyünlərin nömrələri və bu ipin tamamilə (bir ucundan başlayaraq digər ucuna qədər) yanacağı vaxtı ehtiva edir.

Hər bir düyün cütlüyünü maksimum bir ip birləşdirir. Əgər fitilin hər hansı bir düyünü yandırılarsa, onun tamamilə yanacağına zəmanət verilir.

Çıxış verilənləri

Çıxış faylına yandırılacaq düyünün nömrəsini və bütün fitilin tamamilə yanacağı zamanı ifadə edən iki ədəd verin.