eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

ACM змагання і порушення звязку

ACM змагання і порушення звязку

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Для підготовки до "Першого національного шкільного ACM змагання" (у 20??) мер міста вирішив забезпечити всі школи надійним джерелом енергії. (Мер дуже побоюється порушень зв'язку). Для цього електростанція "Майбутнє" і одна зі шкіл (не грає ролі яка) повмнні бути з'єднані; а також деякі інші школи також повинні бути приєднані до мережі.

Школа має достатньо електроенергії, якщо або вона під'єднана напряму до електростанції "Майбутнє", або до іншої школи, яка має достатньо електроенергії. Вам віжома віртість з'єднання деяких шкіл одна з одною. Мер хоче знайти два найдешевших плани з'єднання шкіл. Вартість плану рівна сумі вартостей всіх з'єнань між школами, що входять до ньго. Допоможіть меру знайти ці два найдешевших плани.

Вхідні дані

Перший рядок містить два числа, відокремлених одним пропуском: n (3n100) - кількість шкіл у місті і m - кількість наявних зв'язків між ними. Кожен з наступних m рядків містить три числа a[i], b[i], c[i], де c[i] (1c[i]300) - вартість зв'язку між школами a[i] та b[i]. Школи пронумеровано цілими числами від 1 до n.

Вихідні дані

У одному рядку вивести два числа, відокремлених одним пропуском: варьлсті двох найдешевших планів з'єднань. Нехай S[1] – найдешевший план, а S[2] другий по дешевості план. Тоді S[1] = S[2] лише якщо це два найдешевших плани, інакше S[1]S[2]. Вважайте, що завжди можна знайти S[1] та S[2].

Приклад

Вхідні дані #1
4 4
1 2 2
1 4 5
1 3 4
2 3 3
Вихідні дані #1
10 11
Вхідні дані #2
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
Вихідні дані #2
110 121
Джерело Літня Школа 2010, Севастополь, день М.Медвєдева