Vrăjitorul Arpsod este deranjat la culme de câinii vecinului. Aceștia au prostul obicei de a veni să-și îngroape oasele în curtea vrăjitorului. Înainte de a lua măsuri drastice împotriva vecinului, Arpsod a decis să construiască un gard despărțitor între cele două curți. Gardul poate fi privit ca un segment de dreaptă de lungime N metri. Astfel, Arpsod a angajat K meseriași pentru a-i construi gardul. Fiind un tărâm cât se poate de democratic, fiecare muncitor a decis că el este dispus să construiască doar o parte din gard pornind de la al x-lea metru și pană la al y-lea metru inclusiv. Fiecare meseriaș cere o anumită sumă de bani pentru lucrarea sa.

Arpsod poate decide să angajeze o parte dintre muncitori, pentru a realiza întregul gard. Dacă doi muncitori angajați au de construit o porțiune comună a gardului, ea va fi lucrată de amândoi, dar fiecare își va primi integral suma solicitată.

Cerința

Ajutați-l pe Arpsod să-și aleagă meseriașii astfel încât gardul să fie construit integral și el să plătească o sumă minimă de bani.

Date de intrare

Pe prima linie a fișierului gard1.in se află două numere naturale separate prin spațiu: N și K, reprezentând lungimea gardului și numărul de meseriași disponibili. Pe următoarele K linii se vor afla trei valori separate prin spațiu x, y, c, corespunzaoare fiecărui meseriaș: acest meseriaș este dispus să construiască gardul pornind de la al x-lea metru pană la al y-lea metru inclusiv, cerând pentru lucrarea sa prețul c.

Date de ieșire

In fișierul gard1.out se va scrie pe prima linie o singură valoare naturală reprezentând costul minim pe care îl poate plăti Arpsod pentru a i se construi integral gardul.

Restricții și precizări

• 1 ≤ N, K ≤ 100.000
• 1 ≤ x ≤ y ≤ N
• 1 ≤ c ≤ 1.000.000
• Se garantează că mereu există soluție.
• Se garantează că pentru 20% din teste 1 ≤ K ≤ 10 și 1 ≤ c ≤ 3000
• Se garantează că pentru alte 30% din teste 1 ≤ N, K ≤ 1000 și 1 ≤ c ≤ 30000

Exemplu:

gard1.in

10 6
1 7 5
2 3 2
5 8 1
6 9 4
9 10 2
10 10 3

gard1.out

8

Explicație

Se aleg bucățile

1..7 cu cost 5
5..8 cu cost 1
9..10 cu cost 2