Квитки#11228
Бесі планує вирушити на екскурсію. Її маршрут складається з 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 рядків, по одному для кожного пункту.
Приклад 1
Якщо Бесі починає з пункту i = 4, існує лише один спосіб отримати доступ до всіх пунктів від 1 до n, і він такий:
Купити перший квиток у пункті 4, що надає доступ до пунктів 2 і 3.
Купити третій квиток у пункті 2, що надає доступ до пункту 7.
Повернутися в пункт 4 і купити другий квиток, що надає доступ до пунктів 5 і 6.
Купити четвертий квиток у пункті 6, що надає доступ до пункту 1.