Центральна дільниця
Limits: 2 sec., 256 MiB
Усі проблеми, як завжди, через вибори! Наголосували тут усі, а хто ж має ці голоси рахувати? Працівники маленьких дільниць швидко збагнули, що це справа важка й невдячна, а тому вирішили передати усі бюлетені на підрахунок до центральної дільниці (це дільниця з номером 1).
У Країні є \(n\) виборчих дільниць, пронумерованих від 1 до \(n\), та \(m\) доріг між ними.
Компанії "КрПошта", що займається швидкими перевезеннями бюлетенів по усій Країні, потрібно відправити по одній вантажівці з кожної дільниці до центральної, щоб вчасно завершити доставку. Логісти компанії довго намагалися порахувати мінімальну сумарну відстань, яку проїдуть їхні вантажівки. На жаль, вони так і не впоралися, а чи зможете Ви?
Input
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість дільниць та кількість доріг.
У кожному з наступних \(m\) рядків задано по три цілих числа — \(a_i\), \(b_i\), \(c_i\). Ця трійка означає, що між дільницями \(a_i\) та \(b_i\) існує дорога довжиною \(c_i\).
Output
Єдине число — відповідь на задачу.
Constraints
\(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\),
для кожної дільниці існує шлях від неї до центральної.
Samples
Input (stdin) | Output (stdout) |
---|---|
5 6 1 2 3 1 4 2 1 3 7 2 5 1 2 3 1 4 5 1 | 12 |
Notes
Порахуємо найкоротшу відстань від кожної дільниці до центральної:
відстань від 2-ї дільниці рівна 3
відстань від 3-ї дільниці рівна 4
відстань від 4-ї дільниці рівна 2
відстань від 5-ї дільниці рівна 3
сумарна відстань \(=3+4+2+3=12\)
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|