تكلفة الاتصال بين بعض أزواج المدارس معروفة. قرر رئيس بلدية المدينة اختيار أحد أكثر مخططين اقتصاديين لتزويد الطاقة (تكلفة النظام تساوي مجموع تكاليف توصيل أزواج المدارس).
اكتب برنامجًا يحسب تكلفة مخططي إمداد الطاقة البديلين الأكثر فعالية من حيث التكلفة للمدارس.
& nbsp؛
إدخال
يحتوي السطر الأول من ملف الإدخال على رقمين طبيعيين مفصولين بمسافة: N (3 & lt؛ = & nbsp؛ N & lt؛ = 100) ، عدد المدارس في المدينة ، و M & ndash؛ عدد الاتصالات الممكنة بينهما. يحتوي كل سطر من سطور M التالية على ثلاثة أرقام: A i ، B i ، C i ، مفصولة بمسافات ، حيث C i & nbsp؛ - & nbsp؛ تكلفة مد خط كهرباء (1 & lt؛ = & nbsp؛ C i & lt؛ = 300) من المدرسة A i إلى المدرسة B i < / sub> (i = 1،2، & hellip؛، N).
& nbsp؛
الإخراج
يجب أن يحتوي السطر الفردي لملف الإخراج على رقمين طبيعيين
S 1 و
S 2 مفصول بينهما بـ مسافة & - أقل تكلفة للدائرة (S
1 & nbsp؛ & lt؛ = & nbsp؛ S
2 ).
S 1 = S 2 إذا وفقط إذا كان هناك العديد من أنظمة إمداد الطاقة الموثوقة الأقل تكلفة.
& nbsp؛
نضمن وجود نوعين مختلفين من مخططات الإمداد بالطاقة الموثوقة لبيانات الإدخال.
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 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 |