import sys

import heapq

input = sys.stdin.readline





def dijkstra(s, E):

    inf = float('inf')

    d = [inf for i in range(len(E))]

    d[s] = 0

    q = [(0, s)]

    heapq.heapify(q)

    while q:

        c, p = heapq.heappop(q)

        if d[p] < c:

            continue

        for cost, to in E[p]:

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

                d[to] = d[p] + cost

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

    return d





def main():

    N, M = list(map(int, input().split()))

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

    for _ in range(M):

        s, t, c = list(map(int, input().split()))

        E[s-1].append([c, t-1])

    for i in range(N-1):

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



    A = dijkstra(0, E)



    ans = A[N-1]

    if ans == float("inf"):

        print((-1))

    else:

        print(ans)





if __name__ == '__main__':

    main()

import sys

import heapq

input = sys.stdin.readline





def dijkstra(s, E):

    inf = float('inf')

    d = [inf for i in range(len(E))]

    d[s] = 0

    q = [(0, s)]

    while q:

        c, p = heapq.heappop(q)

        if d[p] < c:

            continue

        for cost, to in E[p]:

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

                d[to] = d[p] + cost

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

    return d





def main():

    N, M = list(map(int, input().split()))

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

    for _ in range(M):

        s, t, c = list(map(int, input().split()))

        E[s-1].append((c, t-1))

    for i in range(N-1):

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



    A = dijkstra(0, E)



    ans = A[N-1]

    if ans == float("inf"):

        print((-1))

    else:

        print(ans)





if __name__ == '__main__':

    main()

import sys
import heapq

input = sys.stdin.readline


def dijkstra(s, E):
    inf = float("inf")
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = list(map(int, input().split()))
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = list(map(int, input().split()))
        E[s - 1].append([c, t - 1])
    for i in range(N - 1):
        E[i + 1].append([0, i])
    A = dijkstra(0, E)
    ans = A[N - 1]
    if ans == float("inf"):
        print((-1))
    else:
        print(ans)


if __name__ == "__main__":
    main()

import sys
import heapq

input = sys.stdin.readline


def dijkstra(s, E):
    inf = float("inf")
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = list(map(int, input().split()))
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = list(map(int, input().split()))
        E[s - 1].append((c, t - 1))
    for i in range(N - 1):
        E[i + 1].append((0, i))
    A = dijkstra(0, E)
    ans = A[N - 1]
    if ans == float("inf"):
        print((-1))
    else:
        print(ans)


if __name__ == "__main__":
    main()

-    heapq.heapify(q) -        E[s - 1].append([c, t - 1]) +        E[s - 1].append((c, t - 1)) -        E[i + 1].append([0, i]) +        E[i + 1].append((0, i))