Biletlər#11228
Besi ekskursiyaya hazırlaşır. Marşrut 1-dən n-ə qədər nömrələnmiş n məntəqədən ibarətdir. Satışda k bilet mövcuddur. i-ci bileti c[i] məntəqəsində p[i] qiymətinə almaq olar və bu bilet [a[i], b[i]] aralığındakı məntəqələrə giriş imkanı təmin edir. Hər hansı bir məntəqəyə daxil olmadan əvvəl, Besi həmin məntəqəyə giriş təmin edən bileti almalıdır. Bir dəfə məntəqədə bilet aldıqdan sonra, Besi gələcəkdə istənilən vaxt ora qayıda bilər.
Hər bir i ∈ [1, n] üçün, əgər Besi əvvəlcə yalnız i məntəqəsinə giriş imkanı əldə edibsə, 1 və n məntəqələrinə giriş imkanı əldə etmək üçün tələb olunan minimal ümumi qiyməti tapın. Əgər bu mümkün deyilsə, −1 çıxarın.
Girişin ilk sətiri n (1 ≤ n ≤ 10^5) və k (1 ≤ k ≤ 10^5) ədədlərini ehtiva edir.
Sonrakı k sətirin hər biri dörd tam ədəd c[i] (1 ≤ c[i] ≤ n), p[i] (1 ≤ p[i] ≤ 10^9), a[i] və b[i] (1 ≤ a[i] ≤ b[i] ≤ n) ehtiva edir hər bir i (1 ≤ i ≤ k).
Hər bir məntəqə üçün bir sətir olmaqla n sətir çıxarın.
Əgər Besi i = 4 məntəqəsindən başlayırsa, 1-dən n-ə qədər bütün məntəqələrə giriş imkanı əldə etməyin yalnız bir yolu var və bu belədir:
4 məntəqəsində birinci bileti alın, bu Besiyə 2 və 3 nöqtələrinə giriş imkanı verir.
2 nöqtəsində üçüncü bileti alın, bu Besiyə 7 nöqtəsinə giriş imkanı verir.
4 nöqtəsinə qayıdın və ikinci bileti alın, bu Besiyə 5 və 6 nöqtələrinə giriş imkanı verir.
6 nöqtəsində dördüncü bileti alın, bu Besiyə 1 nöqtəsinə giriş imkanı verir.
Nümunə 1