Problem
इंफॉर्मेटिक्स में ओलंपियाड की तैयारी के लिए, महापौर ने शहर के सभी स्कूलों को विश्वसनीय बिजली आपूर्ति प्रदान करने का निर्णय लिया। ऐसा करने के लिए, बिजली के वैकल्पिक स्रोत “Maibuttya” शहर के किसी एक स्कूल में (इससे कोई फर्क नहीं पड़ता कि कौन सा), साथ ही कुछ स्कूलों को बिजली की लाइनों से एक दूसरे से जोड़ने के लिए।
एक स्कूल को एक विश्वसनीय बिजली आपूर्ति माना जाता है यदि यह सीधे मैबुत्चा स्रोत से जुड़ा है, या उन स्कूलों में से एक है जिसके पास एक विश्वसनीय बिजली आपूर्ति है।
स्कूलों के कुछ जोड़े के बीच कनेक्शन की लागत ज्ञात है। शहर के मेयर ने दो सबसे किफायती बिजली आपूर्ति योजनाओं में से एक को चुनने का फैसला किया (योजना की लागत स्कूलों के जोड़े को जोड़ने की लागत के योग के बराबर है)।
एक प्रोग्राम लिखें जो स्कूलों के लिए दो सबसे अधिक लागत प्रभावी वैकल्पिक बिजली आपूर्ति योजनाओं की लागत की गणना करता है।
इनपुट
इनपुट फ़ाइल की पहली पंक्ति में रिक्त स्थान द्वारा अलग की गई दो प्राकृतिक संख्याएं होती हैं: N (3 <= N <= 100), शहर में स्कूलों की संख्या, और <कोड>एम – उनके बीच संभावित कनेक्शन की संख्या। निम्नलिखित प्रत्येक M पंक्तियों में तीन संख्याएँ होती हैं: Ai, Bi , Ci, रिक्त स्थान द्वारा अलग किया गया, जहां Ci - बिजली लाइन बिछाने की लागत (1 <= Ci <= 300) स्कूल Ai से स्कूल Bi< /उप> (i=1,2,…,N).
आउटपुट
आउटपुट फ़ाइल की एकल पंक्ति में दो प्राकृतिक संख्याएँ होनी चाहिए S1 और S2 द्वारा अलग की गई एक स्थान &ndash ; दो न्यूनतम सर्किट लागतें (S1 <= S2)। S1=S2 अगर और केवल अगर कम लागत वाली विश्वसनीय बिजली आपूर्ति योजनाएं हैं।
यह गारंटी है कि इनपुट डेटा के लिए दो अलग-अलग विश्वसनीय बिजली आपूर्ति योजनाएं हैं।
उदाहरण
<टेबल क्लास = "टेबल-एसएम टेबल-बॉर्डर टेबल-स्ट्राइप्ड टेबल-लिस्ट-टेस्ट">
<सिर>
<थ वर्ग = "अंक"> #
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 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 |