ACM yarışması və rabitə pozulması

"Birinci Milli Məktəb ACM Yarışması"na hazırlıq üçün şəhərin meri bütün məktəblərə etibarlı enerji mənbəyi təmin etmək qərarına gəlib (meri işıqların sönməsindən çox narahatdır). Bunun üçün "Gələcək" elektrik stansiyası və bir məktəb (hansı olduğunun fərqi yoxdur) bir-birinə qoşulmalıdır; əlavə olaraq, bəzi digər məktəblər də bu şəbəkəyə qoşulmalıdırlar.

Bir məktəb, əgər birbaşa "Gələcək" elektrik stansiyasına və ya artıq etibarlı enerji mənbəyi olan digər məktəbə qoşuludursa, etibarlı enerji mənbəyinə malik hesab olunur. Sizə bəzi məktəb cütlərini bir-birinə qoşmağın xərcləri verilir. Mer ən ucuz iki qoşulma planını tapmaq istəyir. Planın xərci, həmin planda daxil edilən bütün birləşmələrin xərclərinin cəminə bərabərdir. Mera bu iki ən ucuz qoşulma planını tapmaqda kömək edin.

Giriş

Birinci sətirdə boşluq ilə ayrılmış iki tam ədədi oxuyursunuz: $n$ (3 \le n \le 100) — şəhərdəki məktəblərin sayı və $m$ — aralarında mövcud olan qoşulmaların sayı. Sonrakı $m$ sətirin hər biri a_i, b_i, c_i ədədlərini ehtiva edir, burada c_i (1 \le c_i \le 300) — a_i və b_i məktəblərinin birləşdirilməsi üçün tələb olunan xərclərdir. Məktəblər $1$-dən $n$-ə qədər nömrələnir.

Çıxış

İki tam ədədi boşluqla ayıraraq çap edin — ən ucuz iki qoşulma planının xərcləri. $S[1]$ ən ucuz qiymət, $S[2]$ isə ondan sonrakıdır. Əgər S[1] = S[2]-dirsə, deməli, iki fərqli ən ucuz plan mövcuddur; əks halda S[1] \le S[2]. Həmişə belə $S[1]$ və $S[2]$ tapmağın mümkün olduğuna zəmanət verilir.