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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = LI()
    G[l - 1] += [(r - 1, c)]


for i in range(n - 1):
    G[i + 1] += [(i, 0)]


def dijkstra(G, s=0):
    hq = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    checked = [0] * n
    while hq:
        min_dist, u = heappop(hq)
        if checked[u]:
            continue
        checked[u] = 1
        for v, c in G[u]:
            if checked[v]:
                continue
            elif dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(hq, (dist[u] + c, v))
    return dist


ans = dijkstra(G)[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from heapq import heappop, heappush

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

INF = float('inf')
def dijkstra(s,n,g): 
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

G = [[] for _ in range(N)]
for i in range(N-1):
  G[i+1].append((i,0))
for l,r,c in LRC:
  l -= 1
  r -= 1
  G[l].append((r,c))

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

Solution (Python):
from heapq import heappop, heappush

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

INF = float('inf')
def dijkstra(s,n,g): 
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush( que,(0,s) )
  while len(que)>0:
    p =  heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for i in range(len(g[v])):
      edge = g[v][i]
      if d[edge[0]] > d[v] + edge[1]:
        d[edge[0]] = d[v] + edge[1]
        heappush( que,(d[edge[0]] , edge[0]) )
  return d

G = [[] for _ in range(N)]
for i in range(N-1):
  G[i+1].append((i,0))
for l,r,c in LRC:
  l -= 1
  r -= 1
  G[l].append((r,c))

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

Solution (Python):
class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))


INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)


for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  
  
  
  
  if p < dp.get(r-1):
    dp.update(r-1,p)
print(dp.get(N-1) if dp.get(N-1) != INF else -1)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


















def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  
    while heap:
        _, v_from = heappop(heap)
        for cost, v_to in graph[v_from]:
            dist_cand = dist[v_from] + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    


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

INF = 10**15
dist = dijkstra(edge, n, 0, INF=INF)
ans = dist[-1] if dist[-1] != INF else -1

print(ans)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


















def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  
    while heap:
        _, v_from = heappop(heap)
        for cost, v_to in graph[v_from]:
            dist_cand = dist[v_from] + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    


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

dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float("inf") else -1

print(ans)

Solution (Python):
import heapq

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

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and not check[-1]:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > d:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

Solution (Python):
def func(x,y):
    return min(x,y)

class SegmentTree:
    def __init__(self, n): 
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [10**18] * (2*self.n-1)

    def update(self, k, a): 
        k += self.n - 1
        self.arr[k] = a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = min(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):
        L, R = l+self.n, r+self.n
        ide_ele = float("inf")
        
         
         
         
         
        res = ide_ele
        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1]) 

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lrc=[tuple(map(int,input().split())) for _ in range(m)]
dp=SegmentTree(n+1)
dp.update(1,0)

rl=[[] for _ in range(n+1)]
rc=[[] for _ in range(n+1)]
for l,r,c in lrc:
    rl[r].append(l)
    rc[r].append(c)

for r in range(2,n+1):
    x=float("inf")
    for l,c in zip(rl[r],rc[r]):
        y=dp.query(l,r)+c
        if x>y:
            x=y
    dp.update(r,x)
    if r==n:
        ans=x

if ans==float("inf"):
    ans=-1
print(ans)

Solution (Python):
def func(x,y):
    return min(x,y)

class SegmentTree:
    def __init__(self, n): 
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [10**18] * (2*self.n-1)

    def update(self, k, a): 
        k += self.n - 1
        self.arr[k] = a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = min(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):
        L, R = l+self.n, r+self.n
        ide_ele = float("inf")
        
         
         
         
         
        res = ide_ele
        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1]) 

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res

n,m=map(int,input().split())
lrc=[tuple(map(int,input().split())) for _ in range(m)]
dp=SegmentTree(n+1)
dp.update(1,0)

rl=[[] for _ in range(n+1)]
rc=[[] for _ in range(n+1)]
for l,r,c in lrc:
    rl[r].append(l)
    rc[r].append(c)

for r in range(2,n+1):
    x=float("inf")
    for l,c in zip(rl[r],rc[r]):
        y=dp.query(l,r)+c
        if x>y:
            x=y
    dp.update(r,x)
    if r==n:
        ans=x

if ans==float("inf"):
    ans=-1
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g
def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,m,g

def dijkstra(s,n,g): 
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,m,g=graphm()
    s=1
    for i in range(n-1):
        a=i+1
        b=i
        g[a].append((b,0))
    
    dis=dijkstra(s,n,g)
    if dis[n-1]==10**15:
        print(-1)
    else:
        print(dis[n-1])
    
if __name__ == "__main__":
    main()

Solution (Python):

import sys




import queue

from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g
def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,m,g

def dijkstra(s,n,g): 
    s -= 1
    que = queue.Queue()
    d = [10**15 for _ in range(n)]
    d[s] = 0
    que.put( (0,s) )
    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                que.put( (d[edge[0]] , edge[0]) )
    return d

def dijkstra1(s,n,g): 
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,m,g=graphm()
    s=1
    for i in range(n-1):
        a=i+1
        b=i
        g[a].append((b,0))
    
    dis=dijkstra1(s,n,g)
    if dis[n-1]==10**15:
        print(-1)
    else:
        print(dis[n-1])
    
if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge[i][2] = 0

x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)

print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))

Solution (Python):
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

n,m=map(int, input().split()) 
route_map = [dict() for _ in range(n)]

for i in range(m):
    u, v, a = map(int, input().split())
    u, v = u - 1, v - 1
    if v in route_map[u].keys():
        a = min(a, route_map[u][v])
    route_map[u][v] = a


    
for i in range(n-1):
    u, v = i+1, i
    route_map[u][v] = 0
    


dijkstra_result = Dijkstra(route_map,0).execute()


if dijkstra_result[-1]!=float('inf'):
    print(dijkstra_result[-1])

else:
    print(-1)

Solution (Python):

from functools import reduce, partial
min = partial(reduce, lambda x, y: x if x < y else y)

class Rmq:
    
    
    
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min([min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r])])
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min([self.layer0[idx], val])

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter
def main():
    inf = 10**18
    N, M, *LRC = map(int, open(0).read().split())
    LRC = list(zip(*[iter(LRC)]*3))
    LRC.sort(key=itemgetter(0))

    idx_LRC = 0
    q = []

    seg = Rmq(N+1, inf=inf)

    seg.set_value(1, 0)
    for v in range(1, N + 1):
        d = seg.get_min(v, N + 1)
        while idx_LRC < M:
            l, r, c = LRC[idx_LRC]
            if l <= v:
                seg.chmin(r, d+c)
                idx_LRC += 1
            else:
                break
    ans = seg[N]
    print(ans if ans != inf else -1)

main()

Solution (Python):
from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))


N, M = inpl()
LRC = sorted([inpl() for _ in range(M)])

points = sorted(list({lrc[i] for i in range(2) for lrc in LRC}))

if points[0] > 1 or points[-1] < N:
    print(-1)
    exit()



dq = [(0,1)]
m = 0 



for i in points:
    
    
    while dq and dq[0][1] < i:
        heappop(dq)
    
    if not dq:
        print(-1)
        break
    
    d = dq[0][0]
    
    while m < M and LRC[m][0] == i:
        heappush(dq, (d+LRC[m][2], LRC[m][1]))
        m += 1
else:
    
    print(d)

Solution (Python):


class Rmq:
    
    
    
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min(self.layer0[idx], val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter
def main():
    N, M, *LRC = map(int, open(0).read().split())
    LRC = list(zip(*[iter(LRC)]*3))
    LRC.sort(key=itemgetter(0))

    idx_LRC = 0
    q = []

    inf = 10**18
    seg = Rmq(N+1, inf=inf)

    seg.set_value(1, 0)
    for v in range(1, N + 1):
        d = seg.get_min(v, N + 1)
        while idx_LRC < M:
            l, r, c = LRC[idx_LRC]
            if l <= v:
                seg.chmin(r, d+c)
                idx_LRC += 1
            else:
                break
    ans = seg[N]
    print(ans if ans != inf else -1)

main()

Solution (Python):

class Rmq:
    
    
    
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min(self.layer0[idx], val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter

N, M, *LRC = map(int, open(0).read().split())
LRC = list(zip(*[iter(LRC)]*3))
LRC.sort(key=itemgetter(0))

idx_LRC = 0
q = []

inf = 10**18
seg = Rmq(N+1, inf=inf)

seg.set_value(1, 0)
for v in range(1, N + 1):
    d = seg.get_min(v, N + 1)
    while idx_LRC < M:
        l, r, c = LRC[idx_LRC]
        if l <= v:
            seg.chmin(r, d+c)
            idx_LRC += 1
        else:
            break
ans = seg[N]
print(ans if ans != inf else -1)

Solution (Python):

class Rmq:
    
    
    
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min(self.layer0[idx], val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter

N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
LRC.sort(key=itemgetter(0))

idx_LRC = 0
q = []

inf = 10**18
seg = Rmq(N+1, inf=inf)

seg.set_value(1, 0)
for v in range(1, N + 1):
    d = seg.get_min(v, N + 1)
    while idx_LRC < M:
        l, r, c = LRC[idx_LRC]
        if l <= v:
            seg.chmin(r, d+c)
            idx_LRC += 1
        else:
            break
ans = seg[N]
print(ans if ans != inf else -1)

Solution (Python):
from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
LRC = sorted([inpl() for _ in range(M)])
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC} | {1,N}))
m = 0
dq = [(0,1)]
for i in points:
    while dq and dq[0][1] < i:
        heappop(dq)
    if not dq:
        print(-1)
        break
    d = dq[0][0]
    while m < M and LRC[m][0] == i:
        heappush(dq, (d+LRC[m][2], LRC[m][1]))
        m += 1
else:
    print(d)

Solution (Python):
from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
LRC = sorted([inpl() for _ in range(M)])
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC} | {1,N}))
m = 0
dq = [(0,1)]
for i in points:
    while dq and dq[0][1] < i:
        heappop(dq)
    if not dq:
        print(-1)
        break
    d = dq[0][0]
    while m < M and LRC[m][0] == i:
        heappush(dq, (d+LRC[m][2], LRC[m][1]))
        m += 1
else:
    print(d)

Solution (Python):
from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
LRC = sorted([(lambda L,R,C:(L-1,R-1,C))(*inpl()) for _ in range(M)])
m = 0
dq = [(0,0)]
for i in range(N):
    while dq and dq[0][1] < i:
        heappop(dq)
    if not dq:
        print(-1)
        break
    d = dq[0][0]
    while m < M and LRC[m][0] == i:
        heappush(dq, (d+LRC[m][2], LRC[m][1]))
        m += 1
else:
    print(d)

Solution (Python):

class Rmq(object):
    __slots__ = ["elem_size", "tree", "real_size"]

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            self.real_size = len(a)
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = tree = [float("inf")] * (elem_size * 2)
            tree[elem_size:elem_size + self.real_size] = a
            for i in range(elem_size - 1, 0, -1):
                tree[i] = min(tree[i << 1], tree[(i << 1) + 1])
        elif isinstance(a, int):
            self.real_size = a
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = [float("inf")] * (elem_size * 2)

    def get_value(self, x: int, y: int) -> int:  
        l, r = x + self.elem_size, y + self.elem_size
        tree = self.tree
        result = float("inf")
        while l < r:
            if l & 1:
                result = min(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = min(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        tree = self.tree
        tree[k] = value
        while k > 1:
            k >>= 1
            tree[k] = min(tree[k << 1], tree[(k << 1) + 1])

    def get_one_value(self, i):
        return self.tree[i+self.elem_size]

    def debug(self):
        print(self.tree[self.elem_size:self.elem_size+self.real_size])


from operator import itemgetter

N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
LRC.sort(key=itemgetter(0))

idx_LRC = 0
q = []

seg = Rmq(N+1)

seg.set_value(1, 0)
for v in range(1, N + 1):
    d = seg.get_value(v, N + 1)
    while idx_LRC < M:
        l, r, c = LRC[idx_LRC]
        if l <= v:
            seg.set_value(r, min(seg.tree[r + seg.elem_size], d + c))
            idx_LRC += 1
        else:
            break
ans = seg.tree[N + seg.elem_size]
print(ans if ans != float("inf") else -1)