مطلوب العثور على شجرة ممتدة ذات وزن أدنى في رسم بياني متصل.
& nbsp؛
إدخال
يحتوي السطر الأول من ملف الإدخال على رقمين طبيعيين n و m - عدد رؤوس وحواف الرسم البياني ، على التوالي (1 & le؛ n & le؛ 20000، 0 & le؛ m & le؛ 100000). تحتوي سطور m التالية على وصف للحواف ، واحد لكل سطر. يتم وصف رقم الحافة i بثلاثة أرقام طبيعية bi و ei و wi - أرقام نهايات الحافة ووزنها ، على التوالي (1 & le؛ bi، ei & le؛ n، 0 & le؛ wi & le؛ 100000).
& nbsp؛
الرسم البياني متصل.
& nbsp؛
الإخراج
اطبع عددًا صحيحًا واحدًا - وزن الحد الأدنى للشجرة الممتدة.
نبسب ؛
<الجسم>
| إدخال
| الإخراج
|
|
4 4
1 2 1
2 3 2
3 4 5
4 1 4
|
7 |