Problem:
 Score : 600 points    Problem Statement We have N points numbered 1 to N arranged in a line in this order.  Takahashi decides to make an undirected graph, using these points as the vertices.
In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph.
The i -th operation is as follows:   The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i . For every pair of integers (s, t) such that L_i \leq s < t \leq R_i , add an edge of length C_i between Vertex s and Vertex t .   The integers L_1, ..., L_M , R_1, ..., R_M , C_1, ..., C_M are all given as input.  Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.      Constraints  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq L_i < R_i \leq N  1 \leq C_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  M  L_1  R_1  C_1  :  L_M  R_M  C_M       Output Print the length of the shortest path from Vertex 1 to Vertex N in the final graph.
If there is no shortest path, print -1 instead.        Sample Input 1 4 3
1 3 2
2 4 3
1 4 6      Sample Output 1 5  We have an edge of length 2 between Vertex 1 and Vertex 2 , and an edge of length 3 between Vertex 2 and Vertex 4 , so there is a path of length 5 between Vertex 1 and Vertex 4 .       Sample Input 2 4 2
1 2 1
3 4 2      Sample Output 2 -1       Sample Input 3 10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3      Sample Output 3 28

Solution (Python):
import sys
input = sys.stdin.readline

class Segment_tree_Lazy:
    
    def __init__(self, n):
        
        self.init(n)
        
        
        self.node = [self.inf]*self.size
        
        self.lazy = [self.inf]*self.size
        
        
    def init(self, n):
        
        self.inf = pow(2, 60)
        self.n = n
        
        self.N = 1
        while self.N < self.n:
            self.N *= 2
            
        self.size = self.N * 2 - 1
        self.N -= 1
        
        
    def evalate(self, k, l, r):
        
        if self.lazy[k] != self.inf:
            self.node[k] = min(self.lazy[k], self.node[k])
            
            if r-l > 1:
                if self.lazy[2*k+1] > self.lazy[k]:
                    self.lazy[2*k+1] = self.lazy[k]
                if self.lazy[2*k+2] > self.lazy[k]:
                    self.lazy[2*k+2] = self.lazy[k]
                
            self.lazy[k] = self.inf
         
            
    def update(self, a, b, x, k=0, l=0, r=-1):
        
        if r < 0:
            r = self.size - self.N
        
        if b <= l or r <= a:
            return 0
        
        if a <= l and r <= b:
            self.lazy[k] = x
            self.evalate(k, l, r)
            return 0
        
        self.update(a, b, x, 2*k+1, l, (l+r)//2)
        self.update(a, b, x, 2*k+2, (l+r)//2, r)
        self.node[k] = min(self.node[2*k+1], self.node[2*k+2])
        
        
    def find(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            return self.inf
        
        self.evalate(k, l, r)
        
        if a <= l and r <= b:
            return self.node[k]
        
        find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
        find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
        return min(find_l, find_r)
    
    
    def count(self, l, r):
        
        return self.find(l, r, 0, 0, self.size-self.N)
    
    
    
    

def main():
    n, m = map(int, input().split())
    
    inf = pow(2, 60)
    dp = [inf]*(n)
    dp[0] = 0
    
    node = [[] for _ in range(n)]
    segment = Segment_tree_Lazy(n)
    
    segment.update(0, 1, 0)
    for i in range(m):
        s, t, c = map(int, input().split())
        node[t-1].append((s-1, c))
        segment.update(s, t, c)
    
    for i in range(n-1):
        dp[i+1] = dp[i] + min(segment.node[segment.N+i+1], segment.lazy[segment.N+i+1])
        for (v, c) in node[i+1]:
            dp[i+1] = min(dp[i+1], dp[v]+c)
        index = i
        while True:
            if dp[index] > dp[index+1]:
                dp[index] = dp[index+1]
                index -= 1
            else:
                break
    
    print(dp[n-1] if dp[n-1] < inf else -1)
    
    
if __name__ == "__main__":
    main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dijkstra(s,graph):
    d = [inf]*n
    d[s] = 0
    h = [(0,s)]
    while h:
        c,v = heappop(h)
        if d[v] < c:
            continue
        for t,cost in graph[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heappush(h,(d[t],t))
    return d

n, m = LI()
edges = [[] for _ in range(n)]
for i in range(1, n):
    edges[i].append((i-1, 0))

for _ in range(m):
    l, r, c = LI()
    edges[l-1].append((r-1, c))

d = dijkstra(0, edges)
if d[-1] == inf:
    print(-1)
else:
    print(d[-1])

Solution (Python):
import heapq
n, m = map(int, input().split())
INF = float('inf')


def dijkstra(s, n, edges):
    d = [INF] * n
    d[s] = 0
    pq = [(0, s)]
    while len(pq) != 0:
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for v2nvc, nv in edges[v]:
            if c + v2nvc < d[nv]:
                d[nv] = c + v2nvc
                heapq.heappush(pq, (d[nv], nv))
    return d


edges = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    edges[l].append((c, r))
for i in range(n - 1):
    edges[i + 1].append((0, i))
d = dijkstra(0, n, edges)
if d[-1] == INF:
    print(-1)
else:
    print(d[-1])

Solution (Python):
N,M=map(int,input().split())

import heapq
def dijkstra_heap(s):
  
  dist=[float("inf")]*size_v
  prev=[-1]*size_v
  used=[False]*size_v
  
  dist[s]=0
  used[s]=True
  

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    
    if used[min_v]:
    
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used[min_v]=True
    
    for v,w in graph[min_v]:
      if not used[v]: 
      
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

size_v=N+1
s=1

graph=[[] for _ in range(size_v)]
for i in range(2,N):
  graph[i].append((i-1,0))
for _ in range(M):
  L,R,C=map(int,input().split())
  graph[L].append((R,C))
  
dist,prev=dijkstra_heap(s)

if dist[N]==float("inf"):
  print(-1)
else:
  print(dist[N])

Solution (Python):
from heapq import heappop, heappush

N, M = map(int, input().split())
adj = [[] for _ in range(N)]

for i in range(N-1):
    adj[i+1].append((i,0))

for i in range(M):
    L, R, C = map(int, input().split())
    adj[L-1].append((R-1,C))

q = [] 
heappush(q,0)
INF = 10**18
d = [INF] * N
d[0] = 0

while len(q) > 0:
    u = heappop(q)
    for v in adj[u]:
        tmp = d[u] + v[1]
        if tmp < d[v[0]]:
            d[v[0]] = tmp
            heappush(q, v[0])

print(d[N-1]) if d[N-1] < INF else print(-1)

Solution (Python):
import heapq

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

V = N
G = [[] for _ in range(V)]    
s = 0

INF = float('inf')

for i in range(V-1):
    G[i+1].append([i, 0])

for _ in range(M):
    l, r, c = map(int,input().split())
    G[l-1].append([r-1, c])

def dijkstra(s):			
    d = [INF for _ in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))

    return d

L = dijkstra(s)

ans = -1 if L[N-1] == INF else L[N-1]

print(ans)

Solution (Python):
import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx+1, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx+1, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import *
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
  G[i+1].append((i,0))
l,r,c=0,0,0
for i in range(M):
  l,r,c=map(int,input().split())
  G[l-1].append((r-1,c))
D=[0]*N
INF=10**200
def ijk(s):
  global D,INF,G
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(0)
if D[-1]>=INF:
  print(-1)
else:
  print(D[-1])

Solution (Python):
from heapq import *
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
  G[i+1].append((i,0))
l,r,c=0,0,0
for i in range(M):
  l,r,c=map(int,input().split())
  G[l-1].append((r-1,c))
D=[0]*N
INF=10**20
def ijk(s):
  global D,INF,G
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(0)
if D[-1]>=INF:
  print(-1)
else:
  print(D[-1])

Solution (Python):
n,m=map(int,input().split())
lrc=[list(map(int,input().split())) for _ in range(m)]
lrc.sort(key=lambda x:x[0])

inf=float('inf')
seen=[inf]*n
seen[0]=0
now=0
from heapq import heappop,heappush
from collections import deque
lrc=deque(lrc)
todo=[[0,now]]
while todo:
  d,v=heappop(todo)
  lst=[]
  while lrc and lrc[0][0]<=v+1:
    lst.append(lrc.popleft())
  for l,r,c in lst:
    if seen[r-1]>seen[v]+c:
      heappush(todo,[seen[v]+c,r-1])
      seen[r-1]=seen[v]+c
if seen[-1]!=inf:
  print(seen[-1])
else:
  print(-1)

Solution (Python):
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for _ in range(m):
        l,r,c = map(int,ipt().split())
        way[l].append((r,c))
    for i in range(1,n):
        way[i+1].append((i,0))
    hq = [(0,1)]
    dst = [10**18]*(n+1)
    dst[1] = 0
    while hq:
        di,qi = hpq.heappop(hq)
        for j,cj in way[qi]:
            if dst[j] > di+cj:
                dst[j] = di+cj
                hpq.heappush(hq,(di+cj,j))
    print((dst[n]+1)%(10**18+1)-1)
    
    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
chk = []
for i in range(m):
  l,r,c = map(int,readline().split())
  chk.append((l-1,r-1,c))
  
chk.sort()
class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)

    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

S = SegmentTree(n,10**14,lambda a,b: min(a,b))
S.update(0,1,0)
for l,r,c in chk:
  a = S.query(l)
  S.update(l,r+1,a+c)
  
ans = S.query(n-1)
if ans == 10**14:
  print(-1)
else:
  print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import *

def dijkstra():
    dist = [10**18]*N
    dist[0] = 0
    pq = []
    heappush(pq, (0, 0))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for i in range(1, N):
    G[i].append((i-1, 0))
    
for _ in range(M):
    L, R, C = map(int, input().split())
    G[L-1].append((R-1, C))

ans = dijkstra()[-1]

if ans==10**18:
    print(-1)
else:
    print(ans)

Solution (Python):
import heapq
import sys
input=sys.stdin.readline

def dijkstra(s,edge):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(n-1):
  edge[i+1].append([0,i])
for _ in range(m):
  u,v,w=map(int,input().split())
  edge[u-1].append([w,v-1])
  edge[v-1].append([w,u-1])
d=dijkstra(0,edge)
if d[n-1]==float('inf'):
  print(-1)
else:
  print(d[n-1])

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    T = read_lists(M)
    T.sort()

    S = []
    C = [10 ** 20] * N
    C[0] = 0
    t = 0
    for i in range(N):
        if i != 0 and len(S) == 0:
            print(-1)
            return

        c, r = (0, 0) if len(S) == 0 else S[0]
        while t < M:
            ll, rr, cc = T[t]
            ll -= 1
            rr -= 1
            if ll > i:
                break
                
            C[rr] = min(C[rr], c + cc)
            heapq.heappush(S, (C[rr], rr))
            t += 1

        while S:
            if S[0][1] > i:
                break
            heapq.heappop(S)

    print(C[-1])


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappop, heappush, heapify

class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.deg[e[1] - indexed] += 1

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

import sys
input = sys.stdin.readline

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

for _ in range(M):
    l, r, c = map(int, input().split())
    E.append((l - 1, r - 1, c))

for i in range(N - 1):
    E.append((i + 1, i, 0))

g = Graph(N, E, 0)
res = g.dijkstra(0)[N - 1]

print(res if res != 10**18 else -1)

Solution (Python):
import heapq
def dijkstra_heap(s,edge,n):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

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

Solution (Python):
from heapq import heappush, heappop

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(1, N):
  graph[i].append((i-1, 0))

for i in range(M):
  l, r, c = map(int, input().split())
  graph[l-1].append((r-1, c))

dist = [-1] * N
d = [(0, 0)]
while d:
  cost, node = heappop(d)
  if dist[node] >= 0:
    continue
  dist[node] = cost
  for child, c in graph[node]:
    if dist[child] >= 0:
      continue
    heappush(d, (cost+c, child))

print(dist[-1])

Solution (Python):

import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

edge=[[] for _ in range(N)]
for i in range(N-1):
    edge[i+1].append((0,i))
for _ in range(M):
    l,r,c=map(int,input().split())
    l-=1
    r-=1
    edge[l].append((c,r))

from heapq import heappop,heappush

def dijkstra(start,n,edges):
    d=[INF]*n
    used=[False]*n
    d[start]=0
    used[start]=True
    edgelist=[]
    for edge in edges[start]:
        heappush(edgelist,edge)
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        d[v]=minedge[0]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,(edge[0]+d[v],edge[1]))
    return d

d=dijkstra(0,N,edge)
print(d[-1] if d[-1]!=INF else -1)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,M=MI()
    inf=10**16

    
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        """
        
        
        
        
        class Edge():
            
            
            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost
        
        def __init__(self, V):
            
            self.G = [[] for _ in range(V)] 
            self. _E = 0 
            self._V = V 
        
        
        def E(self):
            return self._E
        
        
        def V(self):
            return self._V
        
        def add(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1
            
        def add2(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2
            
        def shortest_path(self,s):
            
            
            que = [] 
            d = [inf] * self.V()
            prev = [None]*self.V() 
            d[s] = 0
            heapq.heappush(que,(0,s)) 
            
            while len(que)!=0:
                
                cost,v = heapq.heappop(que)
                
                
                if d[v] < cost:
                    continue
                    
                
                for i in range(len(self.G[v])):
                    e = self.G[v][i] 
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost 
                        prev[e.to] = v
                        heapq.heappush(que,(d[e.to],e.to)) 
            
            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            
                        
            return d
    
    
    djk=Dijkstra(N)

    for i in range(M):
        l,r,c=MI()
        l-=1
        r-=1
        djk.add(l,r,c)
        
    for i in range(1,N):
        djk.add(i,i-1,0)

        
    d=djk.shortest_path(0)
    ans=d[-1]



    
    
    if ans>=inf:
        print(-1)
    else:
        print(ans)
    
        
    
        
        
    

main()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,M=MI()
    inf=10**16
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num




        
        def setL(self,init_val):
            
            for i in range(N):
                self.seg[i+self.num-1]=init_val[i]    
            
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 


        
        def update(self,k,x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])


        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res


    seg=SegTree(N+1,inf,min)
    
    L=[0]*M
    R=[0]*M
    C=[0]*M
    for i in range(M):
        l,r,c=MI()
        l-=1
        r-=1
        L[i]=l
        R[i]=r
        C[i]=c
        
    R,C,L=zip(*sorted(zip(R,C,L)))
        
    
    
    
    now=0
    seg.update(0,0)
    
    for i in range(M):
        r=R[i]
        l=L[i]
        c=C[i]
        m=seg.query(l,now+1)
        
        now=r
        
        
        
        
        if m+c<seg.query(now,now+1):
            seg.update(now,m+c)
        
        
        """
        for ii in range(N):
            print(seg.query(ii,ii+1))"""
        
    ans=seg.query(N-1,N)

    
    
    if ans>=inf:
        print(-1)
    else:
        print(ans)
    
        
    
        
        
    

main()

Solution (Python):
import sys
input = sys.stdin.readline

INF = 10 ** 15

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

LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key = lambda t: (t[1], t[0]))

dp = [INF] * N
dp[0] = 0
for L, R, C in LRCs:
    while dp[R-1] > dp[L-1] + C:
        dp[R-1] = dp[L-1] + C
        R -= 1

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])