Дорожное строительство
Король Мерсер правит королевством 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.
Каждая дорога двунаправленная. Ни одна пара городов не соединена двумя дорогами. 1-й город является столицей королевства.
Конец ввода обозначается строкой, содержащей два нуля, разделенных пробелом. Эту строку не следует обрабатывать как набор данных.
Выходные данные
Для каждого набора данных выведите минимальную стоимость плана, удовлетворяющего условиям, в отдельной строке.