Problem
Để chuẩn bị cho kỳ thi Olympic Tin học, thị trưởng đã quyết định cung cấp nguồn điện đáng tin cậy cho tất cả các trường học trong thành phố. Để làm được điều này, cần phải dẫn một đường dây điện từ một nguồn điện thay thế “Maibuttya” đến một trong các trường trong thành phố (không quan trọng là trường nào), cũng như kết nối một số trường với nhau bằng đường dây điện.
Một trường học được coi là có nguồn điện đáng tin cậy nếu được kết nối trực tiếp với nguồn Maibutcha hoặc với một trong những trường có nguồn điện đáng tin cậy.
Đã biết chi phí kết nối giữa một số cặp trường. Thị trưởng thành phố quyết định chọn một trong hai phương án cấp điện tiết kiệm nhất (chi phí của phương án bằng tổng chi phí nối các cặp trường).
Viết chương trình tính toán chi phí của hai phương án cung cấp điện thay thế hiệu quả nhất về chi phí cho trường học.
Đầu vào
Dòng đầu tiên của tệp đầu vào chứa hai số tự nhiên được phân tách bằng dấu cách: N (3 <= N <= 100), số trường học trong thành phố và M – số lượng các kết nối có thể có giữa chúng. Mỗi dòng M sau đây chứa ba số: Ai, Bi , Ci, được phân tách bằng dấu cách, trong đó Ci - chi phí đặt đường dây điện (1 <= Ci <= 300) từ trường Ai đến trường Bi< /sub > (i=1,2,…,N).
Đầu ra
Dòng duy nhất của tệp đầu ra phải chứa hai số tự nhiên S1 và S2 cách nhau bởi một khoảng trắng &ndash ; hai chi phí mạch thấp nhất (S1 <= S2). S1=S2 khi và chỉ khi có một vài sơ đồ cung cấp điện đáng tin cậy với chi phí thấp nhất.
Chúng tôi đảm bảo rằng có hai sơ đồ cung cấp điện đáng tin cậy khác nhau cho dữ liệu đầu vào.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 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 |