Tanışlıq
Delegasiya məktəblilər N bölgəsindən Ümumrusiya olimpiadasına gəldi. Əslində, "məktəbli qızlar" demək daha dəqiq olardı, çünki bu delegasiya n istedadlı qızdan ibarətdir. Təbii ki, təşkilatçılar bu vəziyyətə hazır deyildilər və yerləşmə gözlənilməz oldu: hər bir məktəbli qız otelin ayrı bir tək nəfərlik otağında yerləşdirildi.
Ertəsi gün eyni oteldə bir neçə başqa nümayəndə heyəti də yerləşdirildi, onlardan birində məktəbli Slava da var idi. O, belə qeyri-adi bir nümayəndə heyətini ötüb keçə bilmədi və turdan əvvəl gecə vaxtı N bölgəsindən olan nümayəndə heyətindən ən azı bir qızla tanış olmaq qərarına gəldi. Slava bilir ki, bu vaxt onlar tura hazırlaşır, kitab oxuyur və qonaq qəbul etməyə hazır deyillər. Buna görə də o, belə hərəkət etməyə qərar verdi. Əvvəlcə o, bir otağın yanındakı elektrik qoruyucusunu söndürəcək, nəticədə orada işıqlar sönəcək. Qaranlıqda qalan qız bir az qorxacaq, sonra isə tur hazırlığını davam etdirmək üçün ən yaxın dostuna gedəcək. Və məhz bu yolda o, ən müdafiəsiz olacaq...
Slava, tanışlıq üçün nə qədər vaxtının ola biləcəyini və bunun üçün hansı qızı seçməli olduğunu bilmək istəyir.
Giriş məlumatları
Girişin ilk sətirində n və k tam ədədləri (1 ≤ n, k ≤ 10^5) - nümayəndə heyətindəki qızların sayı və dost olan qız cütlərinin sayı verilir. Növbəti k sətirdə a[i], b[i] və w[i] ədədləri - dost olan qızların nömrələri və onların otaqları arasındakı məsafə (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i], 1 ≤ w[i] ≤ 10^5) verilir. Heç bir dost cütü iki dəfə təkrarlanmır. Hər bir qızın dostu olduğu təmin edilir.
Çıxış məlumatları
Birinci sətirdə bir tam ədəd çıxarın - tanışlıq üçün özünə təmin edə biləcəyi maksimum vaxt. İkinci sətirdə seçilməli olan məktəbli qızın nömrəsini çıxarın. Əgər maksimum tanışlıq vaxtını təmin edən bir neçə məktəbli qız varsa, onlardan birini çıxarın.