from heapq import heappush, heappop



INF = float("inf")



N, M, *LRC = list(map(int, open(0).read().split()))



E = [[] for _ in range(N)]

for i in range(N - 1):

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

for l, r, c in zip(*[iter(LRC)] * 3):

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



D = [INF] * N

D[0] = 0



Q = [0]

while Q:

    t = heappop(Q)

    dist, cur = divmod(t, N)

    for nxt, cost in E[cur]:

        cand = dist + cost

        if D[nxt] > cand:

            D[nxt] = cand

            heappush(Q, cand * N + nxt)



print((-1 if D[N - 1] == INF else D[N - 1]))
from heapq import heappush, heappop



def main():

    INF = float("inf")



    N, M, *LRC = list(map(int, open(0).read().split()))



    E = [[] for _ in range(N)]

    for i in range(N - 1):

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

    for l, r, c in zip(*[iter(LRC)] * 3):

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



    D = [INF] * N

    D[0] = 0



    Q = [0]

    while Q:

        dist, cur = divmod(heappop(Q), N)

        for nxt, cost in E[cur]:

            cand = dist + cost

            if D[nxt] > cand:

                D[nxt] = cand

                heappush(Q, cand * N + nxt)



    print((-1 if D[N - 1] == INF else D[N - 1]))



main()

from heapq import heappush, heappop

INF = float("inf")
N, M, *LRC = list(map(int, open(0).read().split()))
E = [[] for _ in range(N)]
for i in range(N - 1):
    E[i + 1].append((i, 0))
for l, r, c in zip(*[iter(LRC)] * 3):
    E[l - 1].append((r - 1, c))
D = [INF] * N
D[0] = 0
Q = [0]
while Q:
    t = heappop(Q)
    dist, cur = divmod(t, N)
    for nxt, cost in E[cur]:
        cand = dist + cost
        if D[nxt] > cand:
            D[nxt] = cand
            heappush(Q, cand * N + nxt)
print((-1 if D[N - 1] == INF else D[N - 1]))

from heapq import heappush, heappop


def main():
    INF = float("inf")
    N, M, *LRC = list(map(int, open(0).read().split()))
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        E[i + 1].append((i, 0))
    for l, r, c in zip(*[iter(LRC)] * 3):
        E[l - 1].append((r - 1, c))
    D = [INF] * N
    D[0] = 0
    Q = [0]
    while Q:
        dist, cur = divmod(heappop(Q), N)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, cand * N + nxt)
    print((-1 if D[N - 1] == INF else D[N - 1]))


main()

-INF = float("inf") -N, M, *LRC = list(map(int, open(0).read().split())) -E = [[] for _ in range(N)] -for i in range(N - 1): -    E[i + 1].append((i, 0)) -for l, r, c in zip(*[iter(LRC)] * 3): -    E[l - 1].append((r - 1, c)) -D = [INF] * N -D[0] = 0 -Q = [0] -while Q: -    t = heappop(Q) -    dist, cur = divmod(t, N) -    for nxt, cost in E[cur]: -        cand = dist + cost -        if D[nxt] > cand: -            D[nxt] = cand -            heappush(Q, cand * N + nxt) -print((-1 if D[N - 1] == INF else D[N - 1])) + +def main(): +    INF = float("inf") +    N, M, *LRC = list(map(int, open(0).read().split())) +    E = [[] for _ in range(N)] +    for i in range(N - 1): +        E[i + 1].append((i, 0)) +    for l, r, c in zip(*[iter(LRC)] * 3): +        E[l - 1].append((r - 1, c)) +    D = [INF] * N +    D[0] = 0 +    Q = [0] +    while Q: +        dist, cur = divmod(heappop(Q), N) +        for nxt, cost in E[cur]: +            cand = dist + cost +            if D[nxt] > cand: +                D[nxt] = cand +                heappush(Q, cand * N + nxt) +    print((-1 if D[N - 1] == INF else D[N - 1])) + + +main()