INF = 10 ** 15

MOD = 10 ** 9 + 7 



class SegmentTree():

    f = min

    unit = INF

   

    def __init__(self,array):

        self.N = len(array)

        self.tree = [self.unit] * (2*self.N)

        self._build(array)

    

    def _build(self,array):

        for i,x in enumerate(array,self.N):

            self.tree[i] = x

        for i in range(self.N - 1,0,-1):

            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])

    

    def update(self,k,x):

        k += self.N

        if self.tree[k] <= x:

            return 

        self.tree[k] = x

        while k > 1:

            k >>= 1

            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])

    

    def query(self,l,r):

        l += self.N

        r += self.N

        vl = self.unit

        vr = self.unit

        while l < r:

            if l&1: 

                vl = self.f(vl,self.tree[l])

                l += 1

            if r&1:

                r -= 1

                vr = self.f(self.tree[r],vr)

            l >>= 1

            r >>= 1

        return self.f(vl,vr)

    

    def __str__(self):

        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))



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

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

for _ in range(M):

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

    l -= 1

    r -= 1

    paths[l].append((r,c))



dp = SegmentTree([0] + [INF] * (N - 1))

for l,path in enumerate(paths):

    for r,c in path:

        before_min = dp.query(l,N)

        dp.update(r,before_min + c)

ans = dp.query(N - 1,N)

print((ans if ans < INF else -1))
INF = 10 ** 15

MOD = 10 ** 9 + 7 

from heapq import heappop,heappush,heapify

def dijkstra(G,start = 0):

    N = len(G)

    dist = [INF] *N

    dist[start] = 0

    q = [(0,start)]



    while q:

        d,v = heappop(q)

        if d > dist[v]:

            continue

        for e,c in G[v]:

            if dist[v] + c < dist[e]:

                dist[e] = dist[v] + c

                heappush(q,(dist[e],e))

    return dist[-1]



def main():

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

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

    for _ in range(M):

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

        l -= 1

        r -= 1

        G[l].append((r,c))

        G[r].append((l,c))

    for i in range(N - 1):

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

    ans = dijkstra(G)

    print((ans if ans < INF else -1))

if __name__ == '__main__':

    main()
INF = 10**15
MOD = 10**9 + 7


class SegmentTree:
    f = min
    unit = INF

    def __init__(self, array):
        self.N = len(array)
        self.tree = [self.unit] * (2 * self.N)
        self._build(array)

    def _build(self, array):
        for i, x in enumerate(array, self.N):
            self.tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, k, x):
        k += self.N
        if self.tree[k] <= x:
            return
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1], self.tree[k << 1 | 1])

    def query(self, l, r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l & 1:
                vl = self.f(vl, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.tree[r], vr)
            l >>= 1
            r >>= 1
        return self.f(vl, vr)

    def __str__(self):
        return "\n".join(
            " ".join(str(v) for v in self.tree[1 << i : 1 << (i + 1)])
            for i in range((2 * self.N).bit_length())
        )


N, M = list(map(int, input().split()))
paths = [[] for _ in range(N)]
for _ in range(M):
    l, r, c = list(map(int, input().split()))
    l -= 1
    r -= 1
    paths[l].append((r, c))
dp = SegmentTree([0] + [INF] * (N - 1))
for l, path in enumerate(paths):
    for r, c in path:
        before_min = dp.query(l, N)
        dp.update(r, before_min + c)
ans = dp.query(N - 1, N)
print((ans if ans < INF else -1))

INF = 10**15
MOD = 10**9 + 7
from heapq import heappop, heappush, heapify


def dijkstra(G, start=0):
    N = len(G)
    dist = [INF] * N
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if d > dist[v]:
            continue
        for e, c in G[v]:
            if dist[v] + c < dist[e]:
                dist[e] = dist[v] + c
                heappush(q, (dist[e], e))
    return dist[-1]


def main():
    N, M = list(map(int, input().split()))
    G = [[] for _ in range(N)]
    for _ in range(M):
        l, r, c = list(map(int, input().split()))
        l -= 1
        r -= 1
        G[l].append((r, c))
        G[r].append((l, c))
    for i in range(N - 1):
        G[i + 1].append((i, 0))
    ans = dijkstra(G)
    print((ans if ans < INF else -1))


if __name__ == "__main__":
    main()

+from heapq import heappop, heappush, heapify -class SegmentTree: -    f = min -    unit = INF - -    def __init__(self, array): -        self.N = len(array) -        self.tree = [self.unit] * (2 * self.N) -        self._build(array) - -    def _build(self, array): -        for i, x in enumerate(array, self.N): -            self.tree[i] = x -        for i in range(self.N - 1, 0, -1): -            self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1]) - -    def update(self, k, x): -        k += self.N -        if self.tree[k] <= x: -            return -        self.tree[k] = x -        while k > 1: -            k >>= 1 -            self.tree[k] = self.f(self.tree[k << 1], self.tree[k << 1 | 1]) - -    def query(self, l, r): -        l += self.N -        r += self.N -        vl = self.unit -        vr = self.unit -        while l < r: -            if l & 1: -                vl = self.f(vl, self.tree[l]) -                l += 1 -            if r & 1: -                r -= 1 -                vr = self.f(self.tree[r], vr) -            l >>= 1 -            r >>= 1 -        return self.f(vl, vr) - -    def __str__(self): -        return "\n".join( -            " ".join(str(v) for v in self.tree[1 << i : 1 << (i + 1)]) -            for i in range((2 * self.N).bit_length()) -        ) +def dijkstra(G, start=0): +    N = len(G) +    dist = [INF] * N +    dist[start] = 0 +    q = [(0, start)] +    while q: +        d, v = heappop(q) +        if d > dist[v]: +            continue +        for e, c in G[v]: +            if dist[v] + c < dist[e]: +                dist[e] = dist[v] + c +                heappush(q, (dist[e], e)) +    return dist[-1] -N, M = list(map(int, input().split())) -paths = [[] for _ in range(N)] -for _ in range(M): -    l, r, c = list(map(int, input().split())) -    l -= 1 -    r -= 1 -    paths[l].append((r, c)) -dp = SegmentTree([0] + [INF] * (N - 1)) -for l, path in enumerate(paths): -    for r, c in path: -        before_min = dp.query(l, N) -        dp.update(r, before_min + c) -ans = dp.query(N - 1, N) -print((ans if ans < INF else -1)) +def main(): +    N, M = list(map(int, input().split())) +    G = [[] for _ in range(N)] +    for _ in range(M): +        l, r, c = list(map(int, input().split())) +        l -= 1 +        r -= 1 +        G[l].append((r, c)) +        G[r].append((l, c)) +    for i in range(N - 1): +        G[i + 1].append((i, 0)) +    ans = dijkstra(G) +    print((ans if ans < INF else -1)) + + +if __name__ == "__main__": +    main()