Рабочее место участника

Робинзон, опасаясь хищников, туземцев и пиратов, решил построить свое жилище на высокой скале прямоугольной формы. На поверхности скалы есть несколько горизонтальных уступов, по которым можно свободно ходить. Чтобы добираться до вершины скалы, Робинзон решил прикрепить к камням несколько лиан. Лиана, спускаясь с вершины скалы или одного из уступов, позволяет перемещаться между всеми уступами, через которые или рядом с которыми она проходит. Робинзон может вырастить лианы произвольной длины из семян. Лианы растут на 1 метр в день. Лианы нельзя связывать между собой с целью увеличения длины, так как получившееся соединение не выдерживает вес человека.

Напишите программу, которая вычислит минимальное число дней для выращивания лиан необходимой длины.

В первой строке ввода содержатся два целых числа, разделенных пробелом – высота скалы `H` (`0\ <\ H\ ≤\ 10^6`) и количество уступов `N` (`0\ ≤\ N\ ≤\ 1000`). Далее следует `N` строк, в каждой строке содержатся три целых числа – координаты левого края уступа `L_i` (`0\ ≤\ L_i\ <\ 1000`), координаты правого края уступа `R_i` (`L_i\ <\ R_i\ ≤\ 1000`) и высота уступа `h_i` (`0\ <\ h_i\ <\ H`).

Вывести в первой строке одно целое число – минимальное число дней для выращивания лиан.

100 2
0 50 25
50 70 60

40