Будівництво доріг
Король Мерсер править королівством ACM, яке складається з однієї столиці та кількох міст. Наразі в королівстві немає жодної дороги. Нещодавно король планував побудувати дороги між столицею та містами, але виявив, що вартість будівництва за його планом значно перевищує очікувану.
Щоб зменшити витрати, він вирішив переглянути свій план, видаливши деякі дороги. Проте новий план повинен відповідати таким умовам:
Для кожної пари міст має існувати маршрут (набір доріг), що їх з'єднує.
Мінімальна відстань між столицею та кожним містом не повинна змінюватися порівняно з початковим планом.
Існує багато планів, які можуть відповідати цим умовам, але король Мерсер хоче знайти план з мінімальною вартістю. Ваше завдання — написати програму, яка зчитує початковий план і обчислює вартість нового плану з мінімальною вартістю.
Вхідні дані
Вхід складається з кількох наборів даних. Кожен набір даних має такий формат:
N M u_1 v_1 d_1 c_1 ... u_M v_M d_M c_M
Перший рядок кожного набору даних починається з двох цілих чисел, N та M (1 ≤ N ≤ 10000, 0 ≤ M ≤ 20000). N та M вказують на кількість міст та кількість доріг у початковому плані відповідно.
Наступні M рядків описують інформацію про дороги в початковому плані. i-й рядок містить чотири цілі числа, u_i, v_i, d_i та c_i (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ d_i ≤ 1000, 1 ≤ c_i ≤ 1000). u_i, v_i, d_i та c_i вказують, що існує дорога, яка з'єднує u_i-е місто та v_i-е місто, довжина якої d_i і вартість будівництва якої c_i.
Кожна дорога є двосторонньою. Жодні дві дороги не з'єднують одну й ту ж пару міст. 1-е місто є столицею в королівстві.
Кінець вводу позначається рядком, що містить два нулі, розділені пробілом. Ви не повинні обробляти цей рядок як набір даних.
Вихідні дані
Для кожного набору даних виведіть мінімальну вартість плану, який задовольняє умови, в одному рядку.