Беси собирается на экскурсию. Маршрут состоит из n пунктов пронумерованных 1..n.Имеется k билетов доступных для продажи. i-ый билет можно купить в пункте c[i]
за цену p[i]
и обеспечить себе доступ ко всем пунктам [a[i]
, b[i]
]. Прежде чем войти в любой пункт, Беси должна купить билет который обеспечивает доступ в этот пункт. Купив однажды билет в пункт, Беси может возвращаться в него в любой момент в будущем.
Для каждого i ∈ [1, n], выведите минимальную суммарную цену которую требуется заплатить, чтобы получить доступ к обоим пунктам 1 и n, если изначально Беси имела доступ только к пункту i. Если это невозможно, выведите −1.
Первая строка ввода содержит n (1 ≤ n ≤ 10^5
) и k (1 ≤ k ≤ 10^5
).
Каждая из последующих k строк содержит четыре целых числа c[i]
(1 ≤ c[i]
≤ n), p[i]
(1 ≤ p[i]
≤ 10^9
), a[i]
и b[i]
(1 ≤ a[i]
≤ b[i]
≤ n) для каждого i (1 ≤ i ≤ k).
Выведите n строк, по одной для каждого пункта.
Если Беси стартует из пункта i = 4, существует только один способ получить доступ ко всем пунктам от 1 до n и он таков:
Купить первый билет в пункте 4, что даст Беси доступ к точкам 2 и 3.
Купить третий билет в точку 2, что даёт Беси доступ к точке 7.
Вернуться в точку 4 и купить второй билет, что даст Беси доступ к точкам 5 и 6.
Купить четвёртый билет в точке 6, что даст Беси доступ в точку 1.