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 RangeSpannedGraph(object):
    def __init__(self, n, weighted = False):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        self._weighted = weighted
        N2, N3 = N * 2, N * 3
        ref, _add_edge = self._reflect, self._add_edge
        self.E = [[] for _ in range(N3)]
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            _add_edge(i, cl)
            _add_edge(i, cr)
            _add_edge(ref(cl + N2), i + N2)
            _add_edge(ref(cr + N2), i + N2)

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def add_edge(self, u, v, w = 0):
        self._add_edge(self.to_index(u), self.to_index(v), w)

    def _add_edge(self, u, v, w = 0):
        self.E[u].append((v, w)) if self._weighted else v

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        N2, E = self.N * 2, self.E
        ref, _add_edge = self._reflect, self._add_edge
        while l < r:
            if l & 1:
                _add_edge(ref(l + N2), v, w) if to else _add_edge(v, l, w)
                l += 1
            if r & 1:
                r -= 1
                _add_edge(ref(r + N2), v, w) if to else _add_edge(v, r, w)
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n, weighted = True)
    for _ in range(m):
        l, r, w = map(int, input().split())
        l -= 1
        rsg.add_range_edge(l, r, l, r, w)

    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(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 RangeSpannedGraph(object):
    def __init__(self, n, weighted = False):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        self._weighted = weighted
        N2, N3 = N * 2, N * 3
        ref, _add_edge = self._reflect, self._add_edge
        self.E = [[] for _ in range(N3)]
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            _add_edge(i, cl)
            _add_edge(i, cr)
            _add_edge(ref(cl + N2), i + N2)
            _add_edge(ref(cr + N2), i + N2)

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def add_edge(self, u, v, w = 0):
        self._add_edge(self.to_index(u), self.to_index(v ), w)

    def _add_edge(self, u, v, w = 0):
        self.E[u].append((v, w)) if self._weighted else v

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        N2, E = self.N * 2, self.E
        ref, _add_edge = self._reflect, self._add_edge
        while l < r:
            if l & 1:
                _add_edge(ref(l + N2), v, w) if to else _add_edge(v, l, w)
                l += 1
            if r & 1:
                r -= 1
                _add_edge(ref(r + N2), v, w) if to else _add_edge(v, r, w)
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n, weighted = True)
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        rsg.add_range_edge(u, v, u, v, w)

    
    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(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 RangeSpannedGraph(object):
    def __init__(self, n, weighted = False):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        self._weighted = weighted
        N2, N3 = N * 2, N * 3
        ref, add_edge = self._reflect, self._add_edge
        E = [[] for _ in range(N3)]
        self.E = E
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            add_edge(i, cl)
            add_edge(i, cr)
            add_edge(ref(cl + N2), i + N2)
            add_edge(ref(cr + N2), i + N2)

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def _add_edge(self, u, v, w = 0):
        self.E[u].append((v, w)) if self._weighted else v

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        E, N2 = self.E, self.N * 2
        ref, add_edge = self._reflect, self._add_edge
        while l < r:
            if l & 1:
                add_edge(ref(l + N2), v, w) if to else add_edge(v, l, w)
                l += 1
            if r & 1:
                r -= 1
                add_edge(ref(r + N2), v, w) if to else add_edge(v, r, w)
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n, weighted = True)
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        rsg.add_range_edge(u, v, u, v, w)

    
    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(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 RangeSpannedGraph(object):
    def __init__(self, n):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        N2, N3 = N * 2, N * 3
        ref = self._reflect
        E = [[] for _ in range(N3)]
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            E[i].append((cl, 0))
            E[i].append((cr, 0))
            E[ref(cl + N2)].append((ref(i + N2), 0))
            E[ref(cr + N2)].append((ref(i + N2), 0))
        self.E = E

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        E, ref, N2 = self.E, self._reflect, self.N * 2
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((v, w)) if to else E[v].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((v, w)) if to else E[v].append((r, 0))
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n)
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        rsg.add_range_edge(u, v, u, v, w)

    
    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(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()
from heapq import heappop, heappush

def build():
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

def add_range_edge(l0, r0, l1, r1, w):
    E.append([])
    v = len(E) - 1
    _add_range_edge(l0 + N, r0 + N, v, w, to = True)
    _add_range_edge(l1 + N, r1 + N, v, 0, to = False)

def _add_range_edge(l, r, v, w, to):
    while l < r:
        if l & 1:
            E[ref(l + N2)].append((v, w)) if to else E[v].append((l, w))
            l += 1
        if r & 1:
            r -= 1
            E[ref(r + N2)].append((v, w)) if to else E[v].append((r, w))
        l >>= 1
        r >>= 1

def resolve():
    global N, N2, E, ref
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, N3 = N * 2, N * 3
    E = [[] for _ in range(N3)]
    ref = lambda v : v if v < 3 * N else v - N2

    build()
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        add_range_edge(u, v, u, v, w)

    
    dist = [INF] * (N3 + m)
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + 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()
from heapq import heappop, heappush

def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, N3 = N * 2, N * 3
    E = [[] for _ in range(N3)]
    ref = lambda v : v if v < 3 * N else v - N2

    
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    def add_range_edge(l0, r0, l1, r1, w):
        E.append([])
        v = len(E) - 1
        _add_range_edge(l0 + N, r0 + N, v, w, to = True)
        _add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(l, r, v, w, to):
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((v, w)) if to else E[v].append((l, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((v, w)) if to else E[v].append((r, w))
            l >>= 1
            r >>= 1

    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        add_range_edge(u, v, u, v, w)

    
    dist = [INF] * (N3 + m)
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + 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()
from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, N3 = N * 2, N * 3
    E = [[] for _ in range(N * 3 + m)]
    ref = lambda v : v if v < 3 * N else v - N2

    
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    
    for i in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((N3 + i, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((N3 + i, w))
            l >>= 1
            r >>= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[N3 + i].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[N3 + i].append((r, 0))
            l >>= 1
            r >>= 1

    
    dist = [INF] * (N3 + m)
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + 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()
from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, now = N * 2, N * 3
    E = [[] for _ in range(N * 3 + m)]
    ref = lambda v : v if v < 3 * N else v - N2

    
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((now, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((now, w))
            l >>= 1
            r >>= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[now].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[now].append((r, 0))
            l >>= 1
            r >>= 1
        now += 1

    
    dist = [INF] * now
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Solution (Python):






import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




  
N,M = IL()
data = ILL(M)
graph = [[] for i in range(N)]
for l,r,c in data:
  graph[l-1].append((c,r-1))
for i in range(1,N):
  graph[i].append((0,i-1))
  
def dijkstra(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  f = [False] * N
  q = [(0, start)]
  while q:
    c,u = heapq.heappop(q)
    if f[u]: continue
    d[u] = c
    f[u] = True
    for c,v in graph[u]:
      if not f[v]:
        heapq.heappush(q, (c + d[u], v))
  return d

ans = dijkstra(graph, 0)[-1]

if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):






import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] = val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
N,M = IL()
data = ILL(M)
data.sort()

ST = SegmentTree(N+100,min,INF)
ST.update(1,0)
for l,r,c in data:
  ST.update(r,min(ST.get(r,r+1),ST.get(l,N+10)+c))
  
ans = ST.get(N,N+1)
if ans==INF:
  print(-1)
else:
  print(ans)

Solution (Python):
class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def max_right(self, l, f):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.tree[l])):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.tree[l])
            l += 1
            if (l & -l) == l: break
        return self.n

    def min_left(self, r, f):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r == 0: return 0
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and (r % 2): r >>= 1
            if not f(self.op(self.tree[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r: break
        return 0

    def __getitem__(self, i):
        return self.get(i,i+1)

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])


import sys
input = sys.stdin.readline

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

e = 1<<60
op = lambda x, y: x if x<y else y
st = SegmentTree(N, op, e)
query = []
st.update(0,0)
for _ in range(M):
    L, R, C = map(int, input().split())
    query.append((L-1, R-1, C))
query.sort(key=lambda x:x[1])
for L, R, C in query:
    tmp = st.get(L, R) + C
    if st[R] > tmp:
        st.update(R,tmp)
print(st[N-1] if st[N-1]!=e else -1)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, now = N * 2, N * 3
    E = [[] for _ in range(N * 3 + m * 2)]
    ref = lambda v : v if v < 3 * N else v - N2

    
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((now, 0))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((now, 0))
            l >>= 1
            r >>= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[now + 1].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[now + 1].append((r, 0))
            l >>= 1
            r >>= 1
        
        E[now].append((now + 1, w))
        now += 2

    
    dist = [INF] * now
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + 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()
from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, now = N << 1, N << 2
    E = [[] for _ in range((N << 2) + (m << 1))]

    
    for i in range(N, N2):
        E[i].append((i + N2, 0))
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[cl + N2].append((i + N2, 0))
        E[cr + N2].append((i + N2, 0))

    
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[l + N2].append((now, 0))
                l += 1
            if r & 1:
                r -= 1
                E[r + N2].append((now, 0))
            l >>= 1
            r >>= 1
        
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[now + 1].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[now + 1].append((r, 0))
            l >>= 1
            r >>= 1
        
        E[now].append((now + 1, w))
        now += 2

    
    dist = [INF] * now
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()