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
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10**30
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] 
        dis = q[0] 

        
        
        if d[ver] < dis:
            continue

        
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(ans)

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

INF = 10**30
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] 
        dis = q[0] 

        
        
        if d[ver] < dis:
            continue

        
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(ans)

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


def dijkstra(s, E):
    inf = float('inf')
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, E)

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


if __name__ == '__main__':
    main()

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

INF = 10**20
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] 
        dis = q[0] 

        
        
        if d[ver] < dis:
            continue

        
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, M, *LRC = map(int, open(0).read().split())

    E = [[] for _ in range(N)]
    for i in range(N - 1):
        E[i + 1].append((i, 0))
    for l, r, c in zip(*[iter(LRC)] * 3):
        E[l - 1].append((r - 1, c))

    D = [INF] * N
    D[0] = 0

    Q = [0]
    while Q:
        t = heappop(Q)
        dist, cur = t // N, t % N
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, cand * N + nxt)

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

main()

Solution (Python):
from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, M, *LRC = map(int, open(0).read().split())

    E = [[] for _ in range(N)]
    for i in range(N - 1):
        E[i + 1].append((i, 0))
    for l, r, c in zip(*[iter(LRC)] * 3):
        E[l - 1].append((r - 1, c))

    D = [INF] * N
    D[0] = 0

    Q = [0]
    while Q:
        dist, cur = divmod(heappop(Q), 100010)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, cand * 100010 + nxt)

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

main()

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

INF = 10**20
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] 
        dis = q[0] 

        
        
        if d[ver] < dis:
            continue

        
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))

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

INF = 10**15
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] 
        dis = q[0] 

        
        
        if d[ver] < dis:
            continue

        
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    
    res = [INF] * N
    
    que = [src]
    res[src] = 0
    
    while len(que) != 0:
        
        cur = heappop(que)
        
        dist = cur // N
        cur %= N
        
        for nxt, cost in nodes[cur]:
            
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                
                heappush(que, (dist+cost)*N+nxt)
    
    return res

N, M = MAP()
nodes = [[] for i in range(N)]

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

for i in range(M):
    l, r, c = MAP()
    l -= 1
    r -= 1
    
    nodes[l].append((r, c))

res = dijkstra(N, nodes, 0)

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

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

INF = 10**15
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] 
        dis = q[0] 

        
        
        if d[ver] < dis:
            continue

        
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    
    res = [INF] * N
    
    que = [src]
    res[src] = 0
    
    while len(que) != 0:
        
        cur = heappop(que)
        
        dist = cur // N
        cur %= N
        
        for nxt, cost in nodes[cur]:
            
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                
                heappush(que, (dist+cost)*N+nxt)
    
    return res

N, M = MAP()
nodes = [[] for i in range(N)]

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

for i in range(M):
    l, r, c = MAP()
    l -= 1
    r -= 1
    
    nodes[l].append((r, c))

res = dijkstra(N, nodes, 0)

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

Solution (Python):
import sys
from heapq import heapify, heappush, heappop
read = sys.stdin.read


def main():
    N, M, *LRC = map(int, read().split())
    graph = [[(0, i - 1)] for i in range(N + 1)]
    graph[1] = []

    for L, R, C in zip(*[iter(LRC)] * 3):
        graph[L].append((C, R))

    distance = [-1] * (N + 1)
    queue = []
    heapify(queue)
    heappush(queue, (0, 1))

    while queue:
        cost, node = heappop(queue)
        if distance[node] == -1:
            distance[node] = cost
            for add_cost, next_node in graph[node]:
                if distance[next_node] == -1:
                    heappush(queue, (cost + add_cost, next_node))

    print(distance[-1])


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, M, *LRC = map(int, open(0).read().split())

    E = [[] for _ in range(N)]
    for i in range(N - 1):
        E[i + 1].append((i, 0))
    for l, r, c in zip(*[iter(LRC)] * 3):
        E[l - 1].append((r - 1, c))

    D = [INF] * N
    D[0] = 0

    Q = [0]
    while Q:
        dist, cur = divmod(heappop(Q), N)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, cand * N + nxt)

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

main()

Solution (Python):
from heapq import heappush, heappop

INF = float("inf")

N, M, *LRC = map(int, open(0).read().split())

E = [[] for _ in range(N)]
for i in range(N - 1):
    E[i + 1].append((i, 0))
for l, r, c in zip(*[iter(LRC)] * 3):
    E[l - 1].append((r - 1, c))

D = [INF] * N
D[0] = 0

Q = [0]
while Q:
    t = heappop(Q)
    dist, cur = divmod(t, N)
    for nxt, cost in E[cur]:
        cand = dist + cost
        if D[nxt] > cand:
            D[nxt] = cand
            heappush(Q, cand * N + nxt)

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

Solution (Python):
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline
inf = 10**18 



def dijkstra(repn, start, goal):
    dist = [inf for i in range(N + 1)] 
    
    dist[start] = 0
    q = []                  
    heapq.heappush(q, (0, start)) 

    while q:
        prov_cost, src = heapq.heappop(q) 
        
        
        if dist[src] < prov_cost:
            continue

        
        for dest in repn[src]:
            cost = repn[src][dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost 
                heapq.heappush(q, (dist[dest], dest)) 
                
    return dist[goal]
        



N, M = map(int, input().split())
repn = [defaultdict(list) for _ in range(N + 1)]
for i in range(2, N + 1):
    repn[i][i - 1] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    if repn[l][r] == [] or repn[l][r] > c: 
        repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == inf:
    print(-1)
else:
    print(d)

Solution (Python):
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline
inf = 10**18



def dijkstra(repn, start, goal):
    dist = [inf for i in range(N + 1)] 
    
    dist[start] = 0
    q = []                  
    heapq.heappush(q, (0, start)) 

    while q:
        prov_cost, src = heapq.heappop(q) 
        
        
        if dist[src] < prov_cost:
            continue

        
        for dest in repn[src]:
            cost = repn[src][dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost 
                heapq.heappush(q, (dist[dest], dest)) 
                
    return dist[goal]
        



N, M = map(int, input().split())
repn = [defaultdict(list) for _ in range(N + 1)]
for i in range(2, N + 1):
    repn[i][i - 1] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    if repn[l][r] == [] or repn[l][r] > c: 
        repn[l][r] = c

d = dijkstra(repn, 1, N)

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

Solution (Python):
from heapq import heappush, heappop

INF = float("inf")

N, M, *LRC = map(int, open(0).read().split())

E = [[] for _ in range(N)]
for i in range(N - 1):
    E[i + 1].append((i, 0))
for l, r, c in zip(*[iter(LRC)] * 3):
    E[l - 1].append((r - 1, c))

D = [INF] * N
D[0] = 0

Q = [(0, 0)]
while Q:
    dist, cur = heappop(Q)
    for nxt, cost in E[cur]:
        cand = dist + cost
        if D[nxt] > cand:
            D[nxt] = cand
            heappush(Q, (cand, nxt))

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

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

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

E = sorted(E)


N_ = 2**(len(bin(N))-2)
INF = 10**15 
seg = [INF] * (2*N_-1)


def update(k, a):
    k += N_-1
    seg[k] = a

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


def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return seg[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 min(vl, vr)




update(0, 0)

for i in range(M):
    new = query(E[i][0], E[i][1], 0, 0, N_) + E[i][2]
    if new < seg[E[i][1] + N_-1]:
        update(E[i][1], new)

if seg[N-1+N_-1] == INF:
    print(-1)
else:
    print(seg[N-1+N_-1])

Solution (Python):
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline
inf = 10**18



def dijkstra(repn, start, goal):
    dist = [inf for i in range(N + 1)] 
    
    dist[start] = 0
    q = []                  
    heapq.heappush(q, (0, start)) 

    while q:
        prov_cost, src = heapq.heappop(q) 
        
        
        if dist[src] < prov_cost:
            continue

        
        for dest in repn[src]:
            cost = repn[src][dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost 
                heapq.heappush(q, (dist[dest], dest)) 
                
    return dist[goal]
        



N, M = map(int, input().split())
repn = [defaultdict(list) for _ in range(N + 1)]
for i in range(2, N + 1):
    repn[i][i - 1] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    if repn[l][r] == [] or repn[l][r] > c: 
        repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == inf:
    print(-1)
else:
    print(d)

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

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

E = sorted(E, key=lambda X: X[1])


N_ = 2**(len(bin(N))-2)
INF = 10**15 
seg = [INF] * (2*N_-1)


def update(k, a):
    k += N_-1
    seg[k] = a

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


def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return seg[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 min(vl, vr)




update(0, 0)

for i in range(M):
    new = query(E[i][0], E[i][1], 0, 0, N_) + E[i][2]
    if new < seg[E[i][1] + N_-1]:
        update(E[i][1], new)

if seg[N-1+N_-1] == INF:
    print(-1)
else:
    print(seg[N-1+N_-1])

Solution (Python):
import heapq
import collections
def main():

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

    for _ in range(M):
        L, R, C = map(int, input().split())
        if L-1 in graph and R-1 in graph[L-1]:
            graph[L-1][R-1] = min(graph[L-1][R-1], C)
        else:
            graph[L-1][R-1] = C

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    v = []
    heapq.heappush(v, [0, 0])

    while len(v) > 0:
        d, u = heapq.heappop(v)
        if d > dist[u]: continue
        for w in graph[u]:
            if dist[w] > d + graph[u][w]:
                dist[w] = d + graph[u][w]
                heapq.heappush(v, [dist[w], w])

    if dist[N-1] == float('inf'): return -1

    return dist[N-1]

if __name__ == '__main__':
    
    print(main())

Solution (Python):
import sys


class SegTreeMin:

    def __init__(self, n, max_v):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [max_v] * (n2 << 1)
        self.INF = max_v

    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        result = self.INF
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()

            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue

            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))

        return result


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    seg_tree = SegTreeMin(n, 10 ** 15)
    seg_tree.update(0, 0)
    lrc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    lrc.sort()
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = seg_tree.get_min(l, r)
        seg_tree.update(r, min(tm + c, seg_tree.get_min(r, r + 1)))
    mt = seg_tree.get_min(n-1, n)
    print(mt if mt != 10 ** 15 else -1)


if __name__ == '__main__':
    solve()

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


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

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def compute(self, s, t):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        while q:
            dist_x, x = heapq.heappop(q)
            if x == t:
                return distances, prev_nodes

            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes

    def compute_all(self, s):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        for t in range(self.graph.n_nodes):
            heapq.heappush(q, (distances[t], t))
        while q:
            dist_x, x = heapq.heappop(q)
            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes


n, m = ril()
graph = Graph(n)
for i in range(1, n):
    graph.add_edge(i, i - 1, 0)
for _ in range(m):
    a, b, c = ril()
    graph.add_edge(a - 1, b - 1, c)
dijkstra = Dijkstra(graph)
distances, _ = dijkstra.compute(0, n - 1)
d = distances[-1]
if d == float('inf'):
    print(-1)
else:
    print(d)

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


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

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap, (dist[NextNode], NextNode))
    return dist
    


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

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

print(ans)

Solution (Python):
import heapq

n, m = [int(v) for v in input().split(' ')]

links = []
for i in range(n):
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1
    links[r].append((l, c))

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if (closed & (1 << n0)) != 0:
        continue
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n2))

print("-1")

Solution (Python):
import heapq

def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    
    d = [inf for i in range(n)]
    d[s] = 0

    
    q = [(0,s)]
    heapq.heapify(q)

    
    while q:
        c,p = heapq.heappop(q)

        
        if d[p]<c:
            continue

        
        for cost,to in path[p]:
            
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

n,m = map(int, input().split())
path = [[] for i in range(n)]
for i in range(n-1):
    path[i+1].append([0,i])

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

ans = dijkstra(0,path)[-1]
print(-1 if ans==float('inf') else ans)

Solution (Python):
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

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

d = dijkstra(0, V)
ans = d[N-1]
if ans == INFTY:
    print(-1)
else:
    print(ans)

Solution (Python):




from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)

input=sys.stdin.readline

n,m=map(int,input().split())

def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
    for i in range(1,n+1):
        d[i].append((i-1,0))

    x=DIJKSTRA(1,d)[n]
    if x!=float("inf"):
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Solution (Python):
class segtree():
    def segfunc(x,y):
        return min(x,y)
    
    ide_ele = -1
    n=1
    init_val=[0]*n
    
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

        
        for i in range(self.n):
            self.seg[i+self.num-1]=self.init_val[i]    
        
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            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
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    l,r,c=map(int,input().split())
    Edge.append((l-1,r-1,c))
Edge.sort()
INF=10**15
dp=segtree([INF for i in range(N)],min,INF)
dp.update(0,0)
for i in range(M):
    l,r,c=Edge[i]
    dist=dp.query(l,r+1)
    tmp=dp.query(r,r+1)
    dp.update(r,min(tmp,dist+c))
ans=dp.query(N-1,N)
if ans==INF:
    ans=-1
print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import defaultdict

INF = float('inf')
def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

N, M = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for i in range(N):
    E[i+1][i] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    l, r = l-1, r-1
    E[l][r] = min(c, E[l].setdefault(r, INF))
dist = dijkstra(V, E, 0)
print(dist[N-1] if dist[N-1] != INF else -1)