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
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        E[u].append((v, w))

    tree = SegmentTree([INF] * n, min, INF)
    tree.update(0, 0)
    for v in range(n):
        for nv, w in E[v]:
            tree.update(nv, min(tree[nv], tree.sum(v, nv) + w))

    ans = tree[n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def resolve():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        edges.append((u, v, w))
    edges.sort()

    tree = SegmentTree([INF] * n, min, INF)
    tree.update(0, 0)
    for u, v, w in edges:
        tree.update(v, min(tree[v], tree.sum(u, v) + w))

    ans = tree[n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Solution (Python):
class SegmentTree():
  def __init__(self, n, mapping, id):
    self.n = n
    self.id = id
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [self.id] * (2 * self.size)
    self.mapping = mapping
  
  def get(self, p):
    
    res = self.id
    p += self.size
    for _ in range(self.log+1):
      res = self.mapping(res, self.data[p])
      p >>= 1
    return res

  def set(self, p, x):
    
    p += self.size
    self.data[p] = x

  def range_set(self, l, r, x):
    
    l += self.size
    r += self.size
    while l < r:
      if l & 1:
        self.data[l] = self.mapping(self.data[l], x)
        l += 1
      if r & 1:
        r -= 1
        self.data[r] = self.mapping(self.data[r], x)
      l >>= 1
      r >>= 1

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
id = 10**18
lst = SegmentTree(N,min,id)
lst.set(0,0)
A = [list(map(int, input().split())) for _ in range(M)]
A.sort(key=lambda x:(x[0],x[1]))
for l,r,c in A:
  lst.range_set(l-1,r,lst.get(l-1)+c)
ans = lst.get(N-1)
print(ans if ans<id else -1)

Solution (Python):
class SegmentTree():
  def __init__(self, n, INF):
    self.n = n
    self.INF = INF
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [self.INF] * (2 * self.size)
  
  def get(self, p):
    
    res = self.INF
    p += self.size
    for _ in range(self.log+1):
      res = min(res, self.data[p])
      p >>= 1
    return res

  def set(self, p, x):
    
    p += self.size
    self.data[p] = x

  def range_set(self, l, r, x):
    
    l += self.size
    r += self.size
    while l < r:
      if l & 1:
        self.data[l] = min(self.data[l], x)
        l += 1
      if r & 1:
        r -= 1
        self.data[r] = min(self.data[r], x)
      l >>= 1
      r >>= 1

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
INF = 10**18
lst = SegmentTree(N,INF)
lst.set(0,0)
A = [list(map(int, input().split())) for _ in range(M)]
A.sort(key=lambda x:(x[0],x[1]))
for l,r,c in A:
  lst.range_set(l-1,r,lst.get(l-1)+c)
ans = lst.get(N-1)
print(ans if ans<INF else -1)

Solution (Python):
class LazySegmentTree():
  def __init__(self, n, op, e, mapping, composition, id):
    self.n = n
    self.op = op
    self.e = e
    self.mapping = mapping
    self.composition = composition
    self.id = id
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [e] * (2 * self.size)
    self.lazy = [id] * (self.size)

  def update(self, k):
    self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

  def all_apply(self, k, f):
    self.data[k] = self.mapping(f, self.data[k])
    if k < self.size:
      self.lazy[k] = self.composition(f, self.lazy[k])

  def push(self, k): 
    self.all_apply(2 * k, self.lazy[k])
    self.all_apply(2 * k + 1, self.lazy[k])
    self.lazy[k] = self.id

  def build(self, arr):
    
    for i, a in enumerate(arr):
      self.data[self.size + i] = a
    for i in range(self.size-1,0,-1):
      self.update(i)

  def set(self, p, x):
    
    p += self.size
    
    for i in range(self.log, 0, -1):
      self.push(p >> i)
    self.data[p] = x 
    
    for i in range(1, self.log + 1):
      self.update(p >> i)

  def get(self, p):
    
    p += self.size
    
    for i in range(self.log, 0, -1):
      self.push(p >> i)
    return self.data[p]

  def prod(self, l, r):
    
    if l == r: return self.e
    l += self.size
    r += self.size
    for i in range(self.log, 0, -1):
      if ((l >> i) << i) != l: self.push(l >> i)
      if ((r >> i) << i) != r: self.push(r >> i)
    sml = smr = self.e
    while l < r:
      if l & 1:
        sml = self.op(sml, self.data[l])
        l += 1
      if r & 1:
        r -= 1
        smr = self.op(self.data[r], smr)
      l >>= 1
      r >>= 1
    return self.op(sml, smr)

  def all_prod(self):
    return self.data[1]

  def apply(self, p, f):
    
    p += self.size
    for i in range(self.log, 0, -1):
      self.push(p >> i)
    self.data[p] = self.mapping(f, self.data[p])
    for i in range(1, self.log + 1):
      self.update(p >> i)

  def range_apply(self, l, r, f):
    
    if l == r: return
    l += self.size
    r += self.size
    for i in range(self.log, 0, -1):
      if ((l >> i) << i) != l: self.push(l >> i)
      if ((r >> i) << i) != r: self.push((r - 1) >> i)
    l2 = l
    r2 = r
    while l < r:
      if l & 1:
        self.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        self.all_apply(r, f)
      l >>= 1
      r >>= 1
    l = l2
    r = r2
    for i in range(1, self.log + 1):
      if ((l >> i) << i) != l: self.update(l >> i)
      if ((r >> i) << i) != r: self.update((r - 1) >> i)

  def max_right(self, l, g):
    
    
    if l == self.n: return self.n
    l += self.size
    for i in range(self.log, 0, -1):
      self.push(l >> i)
    sm = self.e
    while True:
      while l % 2 == 0: l >>= 1
      if not g(self.op(sm, self.data[l])):
        while l < self.size:
          self.push(l)
          l = 2 * l
          if g(self.op(sm, self.data[l])):
            sm = self.op(sm, self.data[l])
            l += 1
        return l - self.size
      sm = self.op(sm, self.data[l])
      l += 1
      if (l & -l) == l: return self.n

  def min_left(self, r, g):
    
    
    if r == 0: return 0
    r += self.size
    for i in range(self.log, 0, -1):
      self.push((r - 1) >> i)
    sm = self.e
    while True:
      r -= 1
      while r > 1 and r % 2: r >>= 1
      if not g(self.op(self.data[r], sm)):
        while r < self.size:
          self.push(r)
          r = 2 * r + 1
          if g(self.op(self.data[r], sm)):
            sm = self.op(self.data[r], sm)
            r -= 1
        return r + 1 - self.size
      sm = self.op(self.data[r], sm)
      if (r & -r) == r: return 0

import sys
input = sys.stdin.readline

INF = 10**18

e = INF
id = INF
N, M = map(int, input().split())

lst = LazySegmentTree(N, min, e, min, min, id)
lst.set(0,0)
A = [list(map(int, input().split())) for _ in range(M)]
A.sort(key=lambda x:(x[0],x[1]))
for l,r,c in A:
  lst.range_apply(l-1,r,lst.get(l-1)+c)
ans = lst.get(N-1)
print(ans if ans<INF else -1)

Solution (Python):
import sys
from heapq import heappush,heappop,heapify
read=sys.stdin.readline
INF=10**30

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist

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

G=[[] for _ in range(N)]
for i in range(N-1):
    G[i+1].append((0,i))
    
for i in range(M):
    L,R,C=map(int,read().split())
    L-=1;R-=1
    G[L].append((C,R))
    
dist=dijkstra(G,0,N)
ans=dist[N-1]
print(ans if ans!=INF else -1)

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

class segtree:
    def __init__(self,n,op,e):
        self.e=e
        self.op=op
        self.size=1<<(n-1).bit_length()
        self.SEG=[self.e]*(self.size*2)
    
    def update(self,i,x):
        i+=self.size
        self.SEG[i]=x
        
        while i>0:
            i>>=1
            self.SEG[i]=self.op(self.SEG[i*2],self.SEG[i*2+1])
    
    def get(self,i):
        return self.SEG[i+self.size]
    
    def query(self,l,r):
        l+=self.size
        r+=self.size
        
        lres,rres=self.e,self.e
        
        while l<r:
            if l&1:
                lres=self.op(lres,self.SEG[l])
                l+=1
            
            if r&1:
                r-=1
                rres=self.op(rres,self.SEG[r])
            
            l>>=1
            r>>=1
            
        res=self.op(lres,rres)
        return res

INF=float('inf')
N,M=map(int,read().split())

Q=[]
for i in range(M):
    l,r,c=map(int,read().split())
    Q.append((l-1,r-1,c))
Q.sort(key=lambda x:x[0])

seg=segtree(N,min,INF)
seg.update(0,0)
for L,R,C in Q:
    res=seg.query(L,R)+C
    if seg.get(R)>res:
        seg.update(R,res)
ans=seg.get(N-1)
print(ans if ans!=INF else -1)

Solution (Python):
import sys
from collections import defaultdict
import networkx as nx

input = sys.stdin.buffer.readline

N, M = map(int, input().split())
LR_dict = defaultdict(lambda: 10 ** 9)
for _ in range(M):
    l, r, c = map(int, input().split())
    LR_dict[(l, r)] = min(LR_dict[(l, r)], c)

G = nx.DiGraph()
G.add_nodes_from(range(1, N + 1))
G.add_weighted_edges_from([(x + 1, x, 0) for x in range(1, N)])
G.add_weighted_edges_from((l, r, c) for (l, r), c in LR_dict.items())

try:
    print(nx.dijkstra_path_length(G, 1, N))
except nx.NetworkXNoPath:
    print(-1)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.count = 1
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    if node.data == x:
        node.count += 1
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None:
        if node.count > 1:
            node.count -= 1
        else:
            return node.right
    else:
        node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.count > 1:
                node.count -= 1
            elif node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
lrc = [tuple(map(int,input().split())) for _ in range(M)]
lrc = sorted(lrc)
INF=10**20

class SegTree:
    """ segment tree with point modification and range product. """
    
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)

seg = SegTree(N,min,INF)
seg.set_val(0,0)

for i in range(1,M+1):
  l,r,c = lrc[i-1]
  tmp = seg.fold(l-1,r-1)
  seg.set_val(r-1,min(tmp+c, seg.fold(r-1,r)))

ans = seg.fold(N-1,N)
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





def segfunc(x, y):
    return min(x, y)

ide_ele = float('inf')

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N, M = getNM()
seg = SegTree([float('inf')] * (N + 1), segfunc, ide_ele)
L = [getList() for i in range(M)]
L.sort()
seg.update(0, 0)






for l, r, c in L:
    l -= 1
    r -= 1
    opt = seg.query(l, r)
    vs = seg.query(r, r + 1)
    seg.update(r, min(vs, opt + c))
ans = seg.query(N - 1, N)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
LRC = [tuple(map(int,input().split())) for i in range(M)]

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

import heapq
hq = [(0,0)]
INF = float('inf')
cost = [INF] * N
cost[0] = 0
while hq:
    d,v = heapq.heappop(hq)
    for to,c in es[v]:
        if cost[to] <= d+c: continue
        cost[to] = d+c
        heapq.heappush(hq, (d+c,to))

print(-1 if cost[-1]==INF else cost[-1])

Solution (Python):


import sys
from heapq import heapify, heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def dijkstra_heap(v, start, edge):
    """
    ダイクストラ法
    :param v: 走査するグラフの頂点数
    :param start: 始点
    :param edge: 重み付き隣接リスト。[cost, node]の形で渡す
    :return: 始点から各頂点への最短距離
    """
    res = [f_inf] * v
    res[start] = 0
    checked = [False] * v
    checked[start] = True
    edge_list = []
    for u in edge[start]:
        heappush(edge_list, u)
    while len(edge_list):
        min_edge = heappop(edge_list)
        cost, node = min_edge
        if not checked[node]:
            res[node] = cost
            checked[node] = True
            for next_cost, next_node in edge[node]:
                if not checked[next_node]:
                    heappush(edge_list, [next_cost + cost, next_node])
    return res


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, m = map(int, input().split())
    LRC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: [x[0], x[1]])
    dist = [f_inf] * n
    dist[0] = 0
    seg = SegTree(dist, lambda x, y: min(x, y), f_inf)
    for l, r, c in LRC:
        l -= 1
        r -= 1
        mi = seg.query(l, r)
        if dist[r] > mi + c:
            seg.update(r, mi + c)
            dist[r] = mi + c
    res = dist[-1]
    print(res if res != f_inf else -1)


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

    dist = dijkstra_heap(n, 0, edge)
    print(-1 if dist[-1] == f_inf else dist[-1])


if __name__ == '__main__':
    resolve2()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, m = map(int, input().split())
    LRC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: [x[0], x[1]])
    dist = [f_inf] * n
    dist[0] = 0
    seg = SegTree(dist, lambda x, y: min(x, y), f_inf)
    for l, r, c in LRC:
        l -= 1
        r -= 1
        mi = seg.query(l, r)
        if dist[r] > mi + c:
            seg.update(r, mi + c)
            dist[r] = mi + c
    res = dist[-1]
    print(res if res != f_inf else -1)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    from collections import deque, defaultdict
    N, M = map(int, readline().split())

    edge = defaultdict(list)

    for _ in range(M):
        l, r, c = map(int, readline().split())
        edge[l].append((r, c))
        edge[r].append((l, c))

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

    pq = PriorityQueue()
    pq.push((0, 1))
    dist = defaultdict(lambda: INF)

    while pq:
        cur, u = pq.pop()
        for v, c in edge[u]:
            nc = cur + c
            if nc < dist[v]:
                dist[v] = nc
                pq.push((nc, v))

    if dist[N] != INF:
        print(dist[N])
    else:
        print(-1)


if __name__ == '__main__':
    main()

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

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    for i in range(m):
        s, t, c = map(int, input().split())
        tree[t-1].append((s-1, c))
        tree[s-1].append((t-1, c))
    
    for i in range(n-1):
        tree[i+1].append((i, 0))
    
    ans = [-1]*n
    already = [False]*n
    not_yet = [(0, 0)]
    
    while not_yet:
        value, key = heappop(not_yet)
        if already[key]:
            continue
        already[key] = True
        ans[key] = value
        
        for k, v in tree[key]:
            if already[k]:
                continue
            heappush(not_yet, (v+value, k))
        
    print(ans[n-1])
    
    
    
    
if __name__ == "__main__":
    main()

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

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    for i in range(m):
        s, t, c = map(int, input().split())
        tree[t-1].append((s-1, c))
        tree[s-1].append((t-1, c))
    
    for i in range(n-1):
        tree[i+1].append((i, 0))
    
    ans = [-1]*n
    already = [False]*n
    not_yet = [(0, 0)]
    
    while not_yet:
        value, key = heappop(not_yet)
        if already[key]:
            continue
        already[key] = True
        ans[key] = value
        
        for k, v in tree[key]:
            if already[k]:
                continue
            heappush(not_yet, (v+value, k))
        
    print(ans[n-1])
    
    
    
    
if __name__ == "__main__":
    main()