"Birinci məktəblərarası milli ACM yarışmasına" hazırlıq məqsədi ilə şəhərin meri bütün məktəbləri etibarlı enerji mənbəyi ilə təmin etmək qərarına gəlir (mer rabitənin pozulmasından çox qorxur). Bunun üçün hər hansı bir məktəb (vacib deyil məhz hansı) “Gələcək” elektrostansiyasına qoşulmalı və bəzi başqa məktəblər də şəbəkəyə qoşulmalıdır.

Məktəb yalnız o zaman kifayət qədər enerjiyə malik olur ki, o, ya birbaşa “Gələcək” elektrostansiyasına, ya da kifayət qədər enerjiyə malik olan digər bir məktəbə qoşulsun. Bəzi məktəblərin bir-biri ilə qoşulma dəyəri Sizə məlumdur. Mer məktəblərin qoşulma sistemi üçün ən ucuz iki variant tapmağa çalışır. Ən ucuz iki plan hazırlamaq işində merə kömək edin.

Giriş verilənləri

Birinci sətrə bir-birindən boşluq işarəsi ilə ayrılan iki ədəd yazılıb: n (3 ≤ n ≤ 100) - şəhərdəki məktəblərin sayı və m - onlar arasında mövcud olan əlaqələrin sayı. Sonrakı m sətrin hər birinə üç ədəd yazılıb: ai, bi, ci. Burada ci - (1 ≤ ci ≤ 300) ai və bi məktəbləri arasındakı qoşulma dəyəridir. Məktəblər 1-dən n-ə qədər tam ədədlərlə nömrələnib.

Çıxış verilənləri

Çıxışa, bir-birindən boşluq işarəsi ilə ayrılan iki ədəd - ən ucuz iki birləşmə planının dəyəri verilir. Tutaq ki, S1 - ən ucuz, S2 isə ucuzluğa görə ikincidir, o zaman S1 = S2 olarsa, onlar ən ucuz olmalıdır, əks halda isə S1 ≤ S2 qəbul edilir. Elə hesab edin ki, S1 və S2 həmişə tapıla bilər.