e-olymp
Yarışlar

Spanning Tree + DSU

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 (3n100) - şə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 - (1ci300) aibi 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ə S1S2 qəbul edilir. Elə hesab edin ki, S1S2 həmişə tapıla bilər.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 4
1 2 2
1 4 5
1 3 4
2 3 3
Çıxış verilənləri #1
10 11
Giriş verilənləri #2
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Çıxış verilənləri #2
110 121
Mənbə Летняя Школа 2010, Севастополь, день М.Медведева