Problem
به منظور آمادگی برای المپیاد انفورماتیک، شهردار تصمیم گرفت تمام مدارس شهر را با برق مطمئن تامین کند. برای انجام این کار، لازم است یک خط برق از منبع جایگزین برق “Maibuttya” به یکی از مدارس شهر (مهم نیست کدامیک) و همچنین برخی مدارس را با خطوط برق به یکدیگر متصل کنید.
اگر مدرسه ای به طور مستقیم به منبع مایبوچا یا به یکی از مدارسی که منبع تغذیه قابل اعتمادی دارد متصل باشد، دارای منبع تغذیه قابل اعتماد در نظر گرفته می شود.
هزینه اتصال بین چند جفت مدرسه مشخص است. شهردار شهر تصمیم گرفت یکی از دو طرح تامین برق اقتصادی را انتخاب کند (هزینه طرح برابر است با مجموع هزینه های اتصال جفت مدرسه).
برنامه ای بنویسید که هزینه دو مقرون به صرفه ترین طرح منبع تغذیه جایگزین برای مدارس را محاسبه کند.
ورودی
خط اول فایل ورودی شامل دو عدد طبیعی است که با یک فاصله از هم جدا شده اند: N (3 <= N <= 100)، تعداد مدارس در شهر، و M – تعداد اتصالات ممکن بین آنها. هر یک از خطوط M زیر شامل سه عدد است: Ai، Bi ، Ci، جدا شده با فاصله، جایی که Ci - هزینه گذاشتن خط برق (1 <= Ci <= 300) از مدرسه Ai تا مدرسه Bi< /sub (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 |