from operator import itemgetter

inf = float('inf')



n,m = list(map(int, input().split()))

a = [list(map(int, input().split())) for i in range(m)]



a.sort(key=itemgetter(2))

a.sort(key=itemgetter(1))

a.sort(key=itemgetter(0))



d = [inf]*(n+1)

d[1]=0

for i in range(m):

    l,r,c = a[i]

    if d[l]==inf:

        print((-1))

        exit()

    for j in range(r-l):

        if d[r-j]>d[l]+c:

            d[r-j]=d[l]+c

        else:

            break

print((d[n]if d[n]!=inf else -1))
import heapq



def dijkstra(s,path):

    inf = float('inf')

    n = len(path)



    # 距離をinfで初期化

    d = [inf for i in range(n)]

    d[s] = 0



    # sへの距離は0

    q = [(0,s)]

    heapq.heapify(q)



    # 距離が最小の頂点から更新していけば良い

    while q:

        c,p = heapq.heappop(q)



        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue

        if d[p]<c:

            continue



        # 頂点pから伸びる、全ての辺の距離を確認

        for cost,to in path[p]:

            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加

            if d[to] > d[p] + cost:

                d[to] = d[p]+cost

                heapq.heappush(q,(d[to], to))

    return d



n,m = list(map(int, input().split()))

path = [[] for i in range(n)]

for i in range(n-1):

    path[i+1].append([0,i])



for i in range(m):

    l,r,c = list(map(int, input().split()))

    path[l-1].append([c,r-1])



ans = dijkstra(0,path)[-1]

print((-1 if ans==float('inf') else ans))
from operator import itemgetter

inf = float("inf")
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(m)]
a.sort(key=itemgetter(2))
a.sort(key=itemgetter(1))
a.sort(key=itemgetter(0))
d = [inf] * (n + 1)
d[1] = 0
for i in range(m):
    l, r, c = a[i]
    if d[l] == inf:
        print((-1))
        exit()
    for j in range(r - l):
        if d[r - j] > d[l] + c:
            d[r - j] = d[l] + c
        else:
            break
print((d[n] if d[n] != inf else -1))

import heapq


def dijkstra(s, path):
    inf = float("inf")
    n = len(path)
    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0
    # sへの距離は0
    q = [(0, s)]
    heapq.heapify(q)
    # 距離が最小の頂点から更新していけば良い
    while q:
        c, p = heapq.heappop(q)
        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p] < c:
            continue
        # 頂点pから伸びる、全ての辺の距離を確認
        for cost, to in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


n, m = list(map(int, input().split()))
path = [[] for i in range(n)]
for i in range(n - 1):
    path[i + 1].append([0, i])
for i in range(m):
    l, r, c = list(map(int, input().split()))
    path[l - 1].append([c, r - 1])
ans = dijkstra(0, path)[-1]
print((-1 if ans == float("inf") else ans))

-from operator import itemgetter +import heapq -inf = float("inf") + +def dijkstra(s, path): +    inf = float("inf") +    n = len(path) +    # 距離をinfで初期化 +    d = [inf for i in range(n)] +    d[s] = 0 +    # sへの距離は0 +    q = [(0, s)] +    heapq.heapify(q) +    # 距離が最小の頂点から更新していけば良い +    while q: +        c, p = heapq.heappop(q) +        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue +        if d[p] < c: +            continue +        # 頂点pから伸びる、全ての辺の距離を確認 +        for cost, to in path[p]: +            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加 +            if d[to] > d[p] + cost: +                d[to] = d[p] + cost +                heapq.heappush(q, (d[to], to)) +    return d + + -a = [list(map(int, input().split())) for i in range(m)] -a.sort(key=itemgetter(2)) -a.sort(key=itemgetter(1)) -a.sort(key=itemgetter(0)) -d = [inf] * (n + 1) -d[1] = 0 +path = [[] for i in range(n)] +for i in range(n - 1): +    path[i + 1].append([0, i]) -    l, r, c = a[i] -    if d[l] == inf: -        print((-1)) -        exit() -    for j in range(r - l): -        if d[r - j] > d[l] + c: -            d[r - j] = d[l] + c -        else: -            break -print((d[n] if d[n] != inf else -1)) +    l, r, c = list(map(int, input().split())) +    path[l - 1].append([c, r - 1]) +ans = dijkstra(0, path)[-1] +print((-1 if ans == float("inf") else ans))