Problem
Belediye başkanı, Bilişim Olimpiyatı'na hazırlanmak için şehirdeki tüm okullara güvenilir güç kaynağı sağlamaya karar verdi. Bunu yapmak için alternatif bir elektrik kaynağı olan “Maibuttya”dan bir elektrik hattı çekmek gerekir. şehirdeki okullardan birine (hangisi olduğu önemli değil) ve ayrıca bazı okulları elektrik hatlarıyla birbirine bağlamak.
Bir okul, doğrudan Maibutcha kaynağına veya güvenilir bir güç kaynağına sahip okullardan birine bağlıysa, güvenilir bir güç kaynağına sahip olarak kabul edilir.
Bazı okul çiftleri arasındaki bağlantı maliyeti biliniyor. Şehrin belediye başkanı, en ekonomik iki güç kaynağı planından birini seçmeye karar verdi (planın maliyeti, okul çiftlerini birbirine bağlama maliyetlerinin toplamına eşittir).
Okullar için en uygun maliyetli iki alternatif güç kaynağı düzeninin maliyetini hesaplayan bir program yazın.
Giriş
Giriş dosyasının ilk satırı boşlukla ayrılmış iki doğal sayı içerir: N (3 <= N <= 100), şehirdeki okul sayısı ve M – aralarındaki olası bağlantıların sayısı. Aşağıdaki M satırlarının her biri üç sayı içerir: Ai, Bi , Ci, boşluklarla ayrılmış, burada Ci - elektrik hattı döşeme maliyeti (1 <= Ci <= 300) Ai okulundan Bi< okuluna /sub > (i=1,2,…,N).
Çıktı
Çıktı dosyasının tek satırı iki doğal sayı S1 ve S2 içermelidir. boşluk &ndash ; en düşük iki devre maliyeti (S1 <= S2). S1=S2 ancak ve ancak birkaç tane en düşük maliyetli güvenilir güç kaynağı şeması varsa.
Giriş verileri için iki farklı güvenilir güç kaynağı şeması olduğu garanti edilir.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
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
|
110 121 |