Autostrady na Euro

Do Euro tylko kilka chwil, a autostrady w rozsypce!

Aby uniknąć blamażu na skalę światową, wypadałoby ukończyć chociaż jedną taką trasę. Generalny Zarząd Dróg Publicznych ogłosił już stosowny przetarg na budowę drogi długiej n  kilometrów, w odpowiedzi otrzymując szereg ofert budowy odcinków autostrady. Każda oferta zawiera współrzędne początku i końca potencjalnego odcinka oraz planowany koszt wykonania. Niestety wybierając do budowy dwa odcinki częściowo pokrywające się (np. [0, 3] i [2, 4] – za odcinek [2,3] płaci się dwa razy), nie otrzyma się żadnego zwrotu kosztów. Bez trudu da się dobrać oferty w sposób pozwalający na zrealizowanie całej trasy, lecz by zminimalizować koszta wybór zlecono wiodącej firmie informatycznej.

 

Wejście

W pierwszym  wierszu wejścia znajdują się dwie liczby naturalne n i m, (1 <= n, m <= 10^6) oznaczające długość autostrady oraz liczbę ofert.
W kolejnych m wierszach znajdują się po trzy liczby całkowite pi, ki, ci(0 <= pi < ki <=  n, 1 <= ci <= 10^6) określające początek, koniec oraz cenę odcinka w i-tej  ofercie.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita będąca najniższym możliwym kosztem budowy drogi.  

 

Test przykładowy

Wejście:
5 4 
0 1 6 
1 5 7 
0 2 5 
2 5 5 

Wyjście:
10
Wybierając odcinki nr 3 i nr 4 zbudujemy całą trasę( [0,2]+[2,5] = [0,5]) płacąc 5+5= 10. Drugą opcją jest wybór odcinków nr  1 i nr 2 ([0, 1]+[1, 5] = [0,5]), lecz kosztuje 6+7 = 13. Trzecią opcją jest wybór odcinków nr 3 i nr 2( [0, 2] + [1,5]=[0,5]   -  [1,2] się nakłada),  a koszt to 5 + 7 = 12.