مطلوب العثور في الرسم البياني المتصل على شجرة ممتدة ذات وزن أدنى يحتوي على حافة معينة.
تنسيق ملف الإدخال:
& nbsp؛
يحتوي السطر الأول من ملف الإدخال على رقمين طبيعيين N ، M - عدد رؤوس الرسم البياني وحوافه ، على التوالي. تحتوي سطور m التالية على وصف للحواف ، واحد لكل سطر. يتم وصف رقم الحافة i بثلاثة أرقام طبيعية Bi و Ei و Wi وأرقام نهايات الحافة ووزنها على التوالي (1 & lt؛ = Bi، Ei & lt؛ = N، 0 & lt؛ = Wi & lt؛ = 2 ^ 32-1. N & lt ؛ = 10 ، M & lt ؛ = 10). يقدم السطر الأخير الحافة المعطاة B، E، W.
& nbsp؛
تنسيق ملف الإخراج:
& nbsp؛
يجب أن يحتوي السطر الوحيد لملف الإخراج على رقم طبيعي واحد - وزن الحد الأدنى للشجرة الممتدة بالحافة المحددة. & nbsp؛
& nbsp؛
الإدخال:
& nbsp؛
4 4
1 2 1
2 3 2
3 4 5
4 1 4
1 4 7
& nbsp؛
الإخراج:
10