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 heapq


def dijkstra(g: list, start, goal=None):
    num = len(g)          
    dist = [float('inf') for i in range(num)]

    dist[start] = 0
    
    q = []
    heapq.heappush(q, (0, start))  

    while q:
        prov_cost, src = heapq.heappop(q)  
        
        if dist[src] < prov_cost:
            continue
        
        for node, cost in g[src]:
            if dist[node] > dist[src] + cost:
                dist[node] = dist[src] + cost
                heapq.heappush(q, (dist[node], node))
    return dist


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

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

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

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

INF = 10**16
D = [INF for _ in range(N)] 
D[0] = 0 
q = [] 
hp.heappush(q, (0, 0))

while q:
    nd, np = hp.heappop(q) 
    if D[np] < nd: 
        continue
    for d, p in graph[np]:
        if D[p] > D[np] + d: 
            D[p] = D[np] + d
            hp.heappush(q, (D[p], p))

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

Solution (Python):
def examA():
    N = I()
    ans = (N-1)//2
    print(ans)
    return

def examB():
    N = I()
    D = LI()
    d = Counter(D)
    loop = max(d.keys())
    if D[0]!=0 or d[0]!=1:
        print(0)
        return

    ans = 1; cur = 1
    for i in range(loop+1):
        if d[i]==0:
            print(0)
            return
        for _ in range(d[i]):
            ans *= cur
            ans %= mod2
        cur = d[i]
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        l, r, c = LI()
        l -=1; r -=1
        V[l].append((r,c))
    for i in range(N-1):
        V[i+1].append((i,0))

    D = Dijkstra(V)
    ans = D.dist[N-1]
    if ans==inf:
        ans = -1
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    lrc = sorted([LI() for _ in range(m)], key=lambda x: (x[0],x[2],-x[1]))
    lrc.append([inf,inf,inf])
    i = 0
    q = [(1,0),(inf,inf)]
    for l in range(1,n):
        while lrc[i][0] < l:
            i += 1
        while lrc[i][0] == l:
            _,r,c = lrc[i]
            i += 1
            qi = bisect.bisect_left(q, (l,-1))
            _, cc = q[qi]
            t = (r, cc+c)
            ti = bisect.bisect_left(q, t)
            if q[ti][1] > t[1] and q[ti-1][0] < r:
                if q[ti][0] == r:
                    q[ti] = t
                else:
                    q.insert(ti, t)
                while q[ti-1][1] > t[1]:
                    del q[ti-1]
                    ti -= 1

    t = q[-2]
    if t[0] < n:
        return -1

    return t[1]


print(main())

Solution (Python):
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append((0,i))
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append((c,r))
    q = [(0,0)]
    heapq.heapify(q)
    path = [-1]*N
    while q:
        c, v = heapq.heappop(q)
        if path[v] >= 0:
            continue
        path[v] = c
        for cost, e in E[v]:
            if path[e] == -1:
                heapq.heappush(q, (c+cost, e))
    print(path[-1])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append((0,i))
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append((c,r))
    q = [(0,0)]
    heapq.heapify(q)
    path = [10**17]*N
    path[0] = 0
    while q:
        _, v = heapq.heappop(q)
        for cost, e in E[v]:
            if path[e] > path[v] + cost:
                path[e] = path[v] + cost
                heapq.heappush(q, (path[e], e))
    if path[N-1] == 10**17:
        print(-1)
    else:
        print(path[N-1])
if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush,heappop
N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
data=[[],[]]+[[[i-1,0]] for i in range(2,N+1)]
for L,R,C in LRC:
    data[L].append([R,C])
dist=[[0,1]]
inf=float("inf")
flag=[inf]*(N+1)
while dist:
    y,x=heappop(dist)
    if flag[x]!=inf:
        continue
    flag[x]=y
    for u in data[x]:
        if flag[u[0]]==inf:
            heappush(dist,[y+u[1],u[0]])
    if flag[N]!=inf:
        break
if flag[N]==inf:
    print(-1)
else:
    print(flag[N])

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

    INF = 10 ** 18

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

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

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

    d = [INF] * (N + 1)

    def dijkstra(s):
        from heapq import heappop, heappush
        d[s] = 0
        pque = []
        heappush(pque, [0, s])
        
        while pque:
            p = heappop(pque)
            v = p[1]
            if d[v] < p[0]:
                continue
            for i in range(len(G[v])):
                e = G[v][i]
                if d[e[1]] > d[v] + e[0]:
                    d[e[1]] = d[v] + e[0]
                    heappush(pque, [d[e[1]], e[1]])

    dijkstra(1)

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

if __name__ == '__main__':
    main()

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

    INF = 10 ** 18

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

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

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

    d = [INF] * (N + 1)

    def dijkstra(s):
        from heapq import heappop, heappush
        d[s] = 0
        pque = []
        heappush(pque, [0, s])
        
        while pque:
            p = heappop(pque)
            v = p[1]
            if d[v] < p[0]:
                continue
            for i in range(len(G[v])):
                e = G[v][i]
                if d[e[1]] > d[v] + e[0]:
                    d[e[1]] = d[v] + e[0]
                    heappush(pque, [d[e[1]], e[1]])

    dijkstra(1)

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

if __name__ == '__main__':
    main()

Solution (Python):
INF = 10 ** 18

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

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

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

d = [INF] * (N + 1)

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

dijkstra(1)

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 9)

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

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

    
    
    
    

    INIT = 10 ** 18 
    MAX_N = 10 ** 6 
    
    data = [INIT] * (2 * MAX_N - 1) 

    
    def func(vl, vr):
        return min(vl, vr)

    def init(n_):
        
        n = 1
        while n < n_:
            n *= 2
        return n

    
    n = init(N)

    def update(k, a): 
        
        k += n - 1
        data[k] = a
        while k > 0: 
            k = (k - 1)//2
            data[k] = func(data[k * 2 + 1], data[k * 2 + 2])

    def query(a, b, k = 0, l = 0, r = n):
        if r <= a or b <= l:
            return INIT
        if a <= l and r <= b:
            return data[k]
        else:
            vl = query(a, b, k * 2 + 1, l, (l + r)//2)
            vr = query(a, b, k * 2 + 2, (l + r)//2, r)
            return func(vl, vr)

    def initialize(A): 
        for i, a in enumerate(A):
            data[i + n - 1] = a
            
        for i in range((2 * n - 3)//2, -1, -1):
            data[i] = func(data[i * 2 + 1], data[i * 2 + 2])

    
    

    def value(index): 
        return data[index + n - 1]

    
    D = [INIT] * N
    D[0] = 0
    
    initialize(D)

    
    
    
    for a, b, c in lst:
        a -= 1
        b -= 1
        tmp = query(a, b)
        if D[b] > tmp + c:
            D[b] = tmp + c
            update(b, tmp + c)
        

    
    print (-1 if D[N - 1] == INIT else D[N - 1])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

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






INIT = 10 ** 18 
MAX_N = 10 ** 6 

data = [INIT] * (2 * MAX_N - 1) 


def func(vl, vr):
    return min(vl, vr)

def init(n_):
    
    n = 1
    while n < n_:
        n *= 2
    return n


n = init(N)

def update(k, a): 
    
    k += n - 1
    data[k] = a
    while k > 0: 
        k = (k - 1)//2
        data[k] = func(data[k * 2 + 1], data[k * 2 + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return INIT
    if a <= l and r <= b:
        return data[k]
    else:
        vl = query(a, b, k * 2 + 1, l, (l + r)//2)
        vr = query(a, b, k * 2 + 2, (l + r)//2, r)
        return func(vl, vr)

def initialize(A): 
    for i, a in enumerate(A):
        data[i + n - 1] = a
        
    for i in range((2 * n - 3)//2, -1, -1):
        data[i] = func(data[i * 2 + 1], data[i * 2 + 2])




def value(index): 
    return data[index + n - 1]


D = [INIT] * N
D[0] = 0

initialize(D)




for a, b, c in lst:
    a -= 1
    b -= 1
    tmp = query(a, b)
    if D[b] > tmp + c:
        D[b] = tmp + c
        update(b, tmp + c)
    


print (-1 if D[N - 1] == INIT else D[N - 1])

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
minans = inf ;ans = 0 ;count = 0 ;pro = 1

L,n=map(int,input().split())
lrc=[]
for i in range(n):
    l,r,c=map(int,input().split()); l-=1; r-=1
    lrc.append((l,r,c))
lrc.sort(key=lambda tup:tup[1])
class Segment_Tree:
    __slots__ = ['ide_ele', 'size', 'num', 'seg', 'segfunc']

    def __init__(self, size, func, element):
        
        self.ide_ele = element
        self.size = size

        
        self.num = 2 ** (self.size - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        
        self.segfunc = func

    def apply(self, apply_seq):
        
        for i in range(self.size):
            self.seg[i + self.num - 1] = apply_seq[i]    
        
        for i in range(self.num - 2, -1, -1) :
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
        
    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k-1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1],  self.seg[k * 2 + 2])
        
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2 
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


dp=[inf]*L; dp[0]=0
seg=Segment_Tree(L,min,inf)
seg.apply(dp)
for l,r,c in lrc:
    dp[r]=min(dp[r],seg.query(l,r)+c)
    seg.update(r,dp[r])
print(dp[L-1] if dp[L-1] != inf else -1)

Solution (Python):
import heapq


class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


class Graph:
    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class ShortestPath:
    """Dijkstra's algorithm : find the shortest path from a vertex
       Complexity: O(E + log(V))
       used in GRL1A(AOJ)
    """

    def __init__(self, G, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (all edge in E must be 0 or positive)
            start: start vertex
            INF: Infinity distance
        """
        self.G, self.INF = G, INF

    class Node:
        def __init__(self, v, cost):
            self.v, self.cost = v, cost

        def __lt__(self, n):
            return self.cost < n.cost

    def dijkstra(self, start, goal=None):
        que = list()
        self.dist = [self.INF] * self.G.V  
        self.prev = [-1] * self.G.V  
        self.dist[start] = 0
        heapq.heappush(que, self.Node(start, 0))

        while len(que) > 0:
            n = heapq.heappop(que)
            if self.dist[n.v] < n.cost:
                continue
            if goal is not None and n.v == goal:
                return
            for e in self.G.E[n.v]:
                if self.dist[n.v] + e.weight < self.dist[e.dst]:
                    self.dist[e.dst] = self.dist[n.v] + e.weight
                    heapq.heappush(que, self.Node(e.dst, self.dist[e.dst]))
                    self.prev[e.dst] = n.v

    def getPath(self, end):
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]


N, M = map(int, input().split())
g = Graph(N)
for i in range(M):
    l, r, c = map(int, input().split())
    g.add_edge(l - 1, r - 1, c)

for i in range(N - 1):
    g.add_edge(i + 1, i, 0)
sp = ShortestPath(g, INF=10 ** 18)

sp.dijkstra(0)
if sp.dist[-1] == 10 ** 18:
    print(-1)
else:
    print(sp.dist[-1])

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

    import numpy as np
    n, m = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[u-1].append([v-1, c]) for u, v, c in abc]
    [g[i+1].append([i, 0]) for i in range(n-1)]

    import heapq

    yen = np.full(n, np.inf)
    h = [(0, 0)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == np.inf:
            yen[i] = d
            for x, y in g[i]:
                heapq.heappush(h, (d+y, x))
    if yen[n-1] == np.inf:
        print(-1)
        return 0
    print(int(yen[n-1]))


main()

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 = 1 << 100
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 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):
class lheapq:
    def __init__(self, p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self, a):
        n = len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t - 1) // 2][1]:
                self.l[t], self.l[(t - 1) // 2] = self.l[(t - 1) // 2], self.l[t]
                t = (t - 1) // 2
            else:
                break

    def heappop(self):
        n = len(self.l)
        if n == 0:
            return [-1, 0]
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t < n:
            child1 = t * 2 + 1
            child2 = t * 2 + 2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                else:
                    break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1, child2 = child2, child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t], self.l[child2] = self.l[child2], self.l[t]
                    t = child2
                else:
                    break
        return ret

    def isnotblank(self):
        if self.l:
            return True
        else:
            return False


def dijkstra(g, n):
    
    

    f = [-1 for _ in range(n)]

    s = 0
    f[0] = 0
    q = lheapq(g[0])
    while True:
        kakutei = q.heappop()
        if kakutei[0] == -1:
            return f
        while f[kakutei[0]] != -1:
            kakutei = q.heappop()
            if kakutei[0] == -1:
                return f
        s = kakutei[0]
        f[s] = kakutei[1]
        for sg, sl in g[s]:
            if f[sg] == -1:
                q.heappush([sg, sl + f[s]])


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

print(dijkstra(g, n)[-1])

Solution (Python):
from heapq import heappush,heappop
n,m=map(int,input().split())
a=[[[i-1,0]]for i in range(n+1)]
a[0]=[]
for i in range(m):
    l,r,c=map(int,input().split())
    a[l].append([r,c])
q=[float("INF")]*(n+1)
q[1]=0
c=[]
heappush(c,[0,1])
while c:
    s,t=heappop(c)
    if t==n:
        print(s)
        break
    for i,j in a[t]:
        if q[i]>s+j:
            q[i]=s+j
            heappush(c,[s+j,i])
else:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

from heapq import heappop, heappush


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

    d = [float("inf") for _ in range(n)]
    d[0] = 0
    h = [(0, 0)]
    while len(h) > 0:
        tmpd, tmpi = heappop(h)
        for toi, tod in edges[tmpi]:
            if d[toi] > tmpd + tod:
                d[toi] = tmpd + tod
                heappush(h, (d[toi], toi))
    
    if d[n - 1] == float("inf"):
        print(-1)
    else:
        print(d[n - 1])
    


if __name__ == '__main__':
    main()

Solution (Python):
class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


I = [int(_) for _ in open(0).read().split()]
N, M = I[:2]
L, R, C = I[2::3], I[3::3], I[4::3]
ti = float('inf')
ST = SegmentTree([0] * 2 + [ti] * (N - 1), min, ti)
for l, r, c in sorted(zip(L, R, C)):
    ST.update(r, min(ST.query(r, r + 1), ST.query(l, r) + c))
ans = ST.query(N, N + 1)
print(-1 if ans == ti else ans)

Solution (Python):
def main():
    class segtree():
        def __init__(self,base,monoid,ini):
            
            
            
            
            self.ini=ini
            
            self.base=base
            self.basesize=len(self.base)
            self.num,self.depth=1,1
            while self.num<self.basesize:
                self.num*=2
                self.depth+=1
            self.num-=1
            
            self.monoid=monoid
            
            self.treesize=self.num+self.basesize
            self.tree=[None]*self.treesize
            
            for i in range(self.num, self.treesize):self.tree[i]=self.base[i-self.num]
            
            for i in range(self.num-1,-1,-1):
                j=2*i+1
                if j>=self.treesize:self.tree[i]=self.ini
                else:self.tree[i]=self.monoid(self.tree[j],self.tree[min(j+1,self.treesize-1)])
        
        
        def max_index(self,index_func):
            
            i=0
            while i<self.num:
                k=2*i+1
                if k+1<self.treesize:
                    if index_func(self.tree[k+1]):
                        i=k+1
                        continue
                if k<self.treesize:
                    if index_func(self.tree[k]):
                        i=k
                        continue
                return -1
            return i-self.num
    
        
        def min_index(self,index_func):
            
            i=0
            while i<self.num:
                k=2*i+1
                if k<self.treesize:
                    if index_func(self.tree[k]):
                        i=k
                        continue
                if k+1<self.treesize:
                    if index_func(self.tree[k+1]):
                        i=k+1
                        continue
                return -1
            return i-self.num
    
        
        def search(self,lower,upper):
            q=[[0,1]]  
            
            ret=self.ini
            while q:
                i,f=q.pop()
                
                
                width=pow(2,self.depth-f)
                
                kagen=(i-pow(2,f-1)+1)*width
                chuo=kagen+width//2
                jogen=kagen+width
                k=2*i+1
                if lower<=kagen and jogen<=upper:
                    ret=self.monoid(ret,self.tree[i])
                    continue
                if k<self.treesize:
                    if lower<=kagen and chuo<=upper:ret=self.monoid(ret,self.tree[k])
                    elif lower<=chuo:q.append([k,f+1])
                if k+1<self.treesize:
                    if lower<=chuo and jogen<=upper:ret=self.monoid(ret,self.tree[k+1])
                    elif chuo<=upper:q.append([k+1,f+1])
            return ret
    
        
        def update(self,index,new_value):
            i=index+self.num
            self.tree[i]=new_value
            temp=new_value
            while i!=0:
                k=(i-1)//2
                if i%2==1:
                    temp=self.monoid(self.tree[min(i+1,self.treesize-1)],temp)
                else:
                    temp=self.monoid(self.tree[i-1],temp)
                if self.tree[k]!=temp:
                    self.tree[k]=temp
                    i=k
                    continue
                break
    
    n,m=map(int,input().split())
    lrc=[list(map(int,input().split())) for _ in [0]*m]
    lrc.sort(key=lambda x:x[1])
    t=segtree([10**15]*n,min,10**15)
    t.update(0,0)
    for l,r,c in lrc:
        t.update(r-1,min(t.search(r-1,r),t.search(l-1,n)+c))
    tt=t.search(n-1,n)
    if tt==10**15:
        print(-1)
        return 0
    print(tt)
main()