ACM yarışması və rabitə pozulması
"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: a[i], b[i], c[i]. Burada c[i] - (1 ≤ c[i] ≤ 300) a[i] və b[i] 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, S[1] - ən ucuz, S[2] isə ucuzluğa görə ikincidir, o zaman S[1] = S[2] olarsa, onlar ən ucuz olmalıdır, əks halda isə S[1] ≤ S[2] qəbul edilir. Elə hesab edin ki, S[1] və S[2] həmişə tapıla bilər.