Центральна дільниця
Обмеження: 2 сек., 256 МіБ
Усі проблеми, як завжди, через вибори! Наголосували тут усі, а хто ж має ці голоси рахувати? Працівники маленьких дільниць швидко збагнули, що це справа важка й невдячна, а тому вирішили передати усі бюлетені на підрахунок до центральної дільниці (це дільниця з номером 1).
У Країні є \(n\) виборчих дільниць, пронумерованих від 1 до \(n\), та \(m\) доріг між ними.
Компанії "КрПошта", що займається швидкими перевезеннями бюлетенів по усій Країні, потрібно відправити по одній вантажівці з кожної дільниці до центральної, щоб вчасно завершити доставку. Логісти компанії довго намагалися порахувати мінімальну сумарну відстань, яку проїдуть їхні вантажівки. На жаль, вони так і не впоралися, а чи зможете Ви?
Вхідні дані
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість дільниць та кількість доріг.
У кожному з наступних \(m\) рядків задано по три цілих числа — \(a_i\), \(b_i\), \(c_i\). Ця трійка означає, що між дільницями \(a_i\) та \(b_i\) існує дорога довжиною \(c_i\).
Вихідні дані
Єдине число — відповідь на задачу.
Обмеження
\(1 \le n \le 10^5\),
\(0 \le m \le 10^5\),
\(1 \le a_i, b_i \le n\),
\(1 \le c_i \le 1000\),
для кожної дільниці існує шлях від неї до центральної.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 6 1 2 3 1 4 2 1 3 7 2 5 1 2 3 1 4 5 1 | 12 |
Примітки
Порахуємо найкоротшу відстань від кожної дільниці до центральної:
відстань від 2-ї дільниці рівна 3
відстань від 3-ї дільниці рівна 4
відстань від 4-ї дільниці рівна 2
відстань від 5-ї дільниці рівна 3
сумарна відстань \(=3+4+2+3=12\)
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|