Давным-давно в древней Полинезии было $$$n$$$ великих островов, соединенных магическими путями. Острова пронумерованы от $$$1$$$ до $$$n$$$. Эти пути не только позволяли путешествовать, но и поддерживали баланс магической энергии, которая питала весь мир.
Однако однажды случилась катастрофа: богиня Те Фити потеряла свое сердце, все магические пути исчезли, а острова остались изолированными друг от друга. Вождь Туи, отчаянно желая восстановить порядок, собрал лучших шаманов. Маги предложили древний ритуал восстановления, согласно которому можно было создавать новые островки — магические узлы. Всего было создано $$$k$$$ новых островков.
Из каждого нового острова $$$n+1, n+2, \ldots, n+k$$$ можно создать какие-то пути на исходные $$$n$$$ островов. Более точно, для каждого $$$i$$$ от $$$1$$$ до $$$k$$$ известны параметры $$$l_i$$$, $$$r_i$$$ и $$$c_i$$$, означающие, что, потратив $$$c_i$$$ энергии, можно создать путь с острова $$$n + i$$$ на остров $$$j$$$, если $$$l_i \le j \le r_i$$$. Разумеется, с каждого нового острова можно провести несколько путей, но за каждый придется отдать $$$c_i$$$ энергии.
Определите, удастся ли с помощью этих путей соединить все $$$n + k$$$ островов в единую сеть, чтобы от каждого острова можно было добраться до любого другого. И, если можно, определите минимальное количество энергии, необходимое для этого.
Если вы справитесь, древняя Полинезия будет спасена, а былая магия вернет островам процветание. Но если вы потерпите неудачу — острова останутся изолированными, и мир навсегда погрузится в хаос. Все зависит от вас!
Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ — количество изначальных и новых островов ($$$1 \le n, k \le 2 \cdot 10^5$$$).
Следующие $$$k$$$ строк описывают возможные пути с новых островов: в $$$i$$$-й из них даны три целых числа $$$l_i$$$, $$$r_i$$$ и $$$c_i$$$ — границы на возможные концы пути и стоимость каждого такого пути ($$$1 \le l_i \le r_i \le n$$$; $$$1 \le c_i \le 10^9$$$).
Если удастся соединить все острова в Полинезии, выведите минимальное необходимое для этого количество энергии. Если же это невозможно, выведите $$$-1$$$.
4 3 1 3 2 1 2 4 2 4 5
20
6 2 4 6 7 1 2 7
-1
100000 4 1 100000 10 1 100000 76 1 100000 12 1 100000 12
1000100