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



Sample input:
4 3
1 3 2
2 4 3
1 4 6


Sample output:
5

Submission status: Wrong Answer

Solution code:
import sys


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        self.n = n
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        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):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.n2
        r = b + self.n2
        while l < r:
            if r & 1:
                result = min(result, self.tree[r])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        result = min(result, self.tree[r])

        return result

    def debug_print(self):
        a = 1
        while a <= self.n2:
            b = a << 1
            print(self.tree[a:b])
            a = b
        print()


INF = 10 ** 18
n, m = map(int, input().split())
segments = [tuple(map(int, line.split())) for line in sys.stdin]
segments.sort()
sgt = SegTreeMin(n, INF)
sgt.update(0, 0)

for l, r, c in segments:
    use_current = sgt.get_min(l - 1, r - 1) + c
    not_current = sgt.get_min(r - 1, r)

    if use_current < not_current:
        sgt.update(r - 1, use_current)

ans = sgt.get_min(n - 1, n)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

root = [[(0, i-1)] for i in range(N+1)] #(cost, vertex)
for i in range(M):
  L, R, C = LRC[i]
  root[L].append((C, R))
#print(root)
data = []
heappush(data, (0, 1)) #(total_cost, vertex)
ans = [MAX_INT]*(N+1)
ans[1] = 0
finished = [False]*(N+1)
finished[0] = True

while data:
  nowcost, v = heappop(data)
  #print(nowcost, v)
  if finished[v] == False:
    finished[v] = True
    for edge, nextv in root[v]:
      if ans[nextv] < nowcost + edge:
        continue
      else:
        ans[nextv] = nowcost + edge
        heappush(data, (nowcost + edge, nextv))
      #print(ans)
if finished[N] == True:
  print(ans[N])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import queue
class Dijkstra:
    def __init__(self,n):
        self.n = n
        self.lengths = [dict() for _ in range(n)]
        self.inf = float('inf')
    def register(self,v1,v2,l,multiple=True):
        self.lengths[v1][v2] = l
        if multiple:
            self.lengths[v2][v1] = l
    def solve(self,s1):
        d = [self.inf for _ in range(self.n)]
        d[s1] = 0
        Q = queue.PriorityQueue()
        Q.put((d[s1],s1))
        while not Q.empty():
            d1,v1 = Q.get()
            for v2,l in self.lengths[v1].items():
                val = d1 + l
                if val < d[v2]:
                    d[v2] = val
                    Q.put((val,v2))
        return d
N,M = map(int,input().split())
LRC = []
for _ in range(M):
    LRC.append(list(map(int,input().split())))
D = Dijkstra(N)
for l,r,c in LRC:
    D.register(l-1,r-1,c,False)
for i in range(N-1):
    D.register(i+1,i,0,False)
ans = D.solve(0)[-1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import queue
class Dijkstra:
    def __init__(self,n):
        self.n = n
        self.lengths = [dict() for _ in range(n)]
        self.inf = float('inf')
    def register(self,v1,v2,l,multiple=True):
        self.lengths[v1][v2] = l
        if multiple:
            self.lengths[v2][v1] = l
    def solve(self,s1):
        d = [self.inf for _ in range(self.n)]
        d[s1] = 0
        Q = queue.PriorityQueue()
        Q.put((d[s1],s1))
        while not Q.empty():
            d1,v1 = Q.get()
            for v2,l in self.lengths[v1].items():
                val = d1 + l
                if val < d[v2]:
                    d[v2] = val
                    Q.put((val,v2))
        return d

N,M = map(int,input().split())
LRC = []
for _ in range(M):
    LRC.append(list(map(int,input().split())))
D = Dijkstra(N)
for l,r,c in LRC:
    D.register(l-1,r-1,c,False)
for i in range(N-1):
    D.register(i+1,i,0,False)
ans = D.solve(0)[-1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#          .g          `
#       .J.,M|  ..+NMMJMMMMNg..     `        `      `   `
#       ?TMa,5.MMMMMMM?MMMMMMMMt    _Z771,   (w.  j771. j_  z  `  `  `  `  `
#      dNHk;.NMMMB3???<ZZZZZW#^  `  _I  (Z  -C?l  j_  O j_  z`                `
#         .dMMM3_1????{ZZZZX=       _Ozr>`  J>.z_ jIz7! j7?7O`
#    `    dMMM!..__1=?>wZZC`        _I _O. (>  ?I j_    j_  z`
#        .MMM%.._Tm,?1>z0^          _C  _1.J`   (:j`    j`  z`   `  `  `  `  `
#        .Hmm..-?=!..``-gNNg-...`                -.
#     `  JMMMz>>????<<..WMMMMMMMMNe              !_                            `
#        ,MMMp?>?<<(;:(yI1rrwVMMMMM| z771.  `(v-  (C71+ (}  (:  `
#         WMMN<<(::;:!dyyIjtrrrdMMM\`O   w~  J<I  (}  (:(}  ({     `  `  `  `
#    `  `  TgMNx;;:;;(yyyyn1trqMMM# .OvO2!  (l.({ (Izv^ (C771{         .. .. .,
#           TMMMNgJ+!dyyyyynjMMMM#! `O _1. .v~`~z.(}    (}  ({    O?z(_.J..o.l,
#            .TMMMMM(MMMMMMMNWMM"    O  `1-(:   (l(}    (}  ({
#     `          ?""WMMMMMMW9^
#       `                                                      `


import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def dijkstra(n, start, nbl):
    """n: 頂点数, start: 始点, nbl: 隣接リスト"""
    import heapq
    WHITE = 1<<5
    GRAY = 1<<10
    BLACK = 1<<15
    INF = 1<<20
    color = [WHITE] * n
    distance = [INF] * n
    # parent = [-1] * n
    q = []

    distance[start] = 0
    heapq.heappush(q, (0, start))
    while len(q) != 0:
        du, u = heapq.heappop(q)
        # print("u: {}, du: {}".format(u, du))
        color[u] = BLACK
        if distance[u] < du:
            continue
        for next, cost in nbl[u]:
            if color[next] != BLACK and distance[u] + cost < distance[next]:
                distance[next] = distance[u] + cost
                color[next] = GRAY
                heapq.heappush(q, (distance[next], next))
    return distance

def main():
    n, m = map(int, input().strip().split())
    nbl = [[] for _ in range(n)]
    for i in range(n-1):
        nbl[i+1].append((i, 0))
    for i in range(m):
        l, r, c = map(int, input().strip().split())
        l -= 1
        r -= 1
        nbl[l].append((r, c))
    d = dijkstra(n, 0, nbl)
    if d[-1] == 1<<20:
        print(-1)
    else:
        print(d[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
path=[[0 if i==j or i==max(j-1,0) else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c
print(path)
seen=[]
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if i not in seen and v==-1:
      v=i
    if i not in seen and dist[i]<dist[v]:
      v=i
  seen.append(v)
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    prev = {}
    q = []
    d = defaultdict(lambda: INF)
    d[s] = 0
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v, w in g[u].items():
            alt = w + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (alt, v))
    return d

@mt
def slv(N, LRC):
    g = defaultdict(dict)

    LRC.sort(key=lambda x: x[2], reverse=True )
    for l, r, c in LRC:
        g[l][r] = c
    
    for i in range(2, N+1):
        g[i][i-1] = 0

    
    d = Dijkstra(g, 1)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    prev = {}
    q = []
    d = defaultdict(lambda: INF)
    d[s] = 0
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v in g[u]:
            alt = g[u][v] + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (alt, v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)

    for l, r, c in LRC:
        g[l][r] = c
    
    for i in range(2, N+1):
        g[i][i-1] = 0

    
    d = Dijkstra(g, 1)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    prev = {}
    q = []
    d = defaultdict(lambda: INF)
    d[s] = 0
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v in g[u]:
            alt = g[u][v] + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (alt, v))
    return d


class D2():
    def __init__(self, graph, start):
        self.g = graph

        self.dist = defaultdict(lambda: INF)
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heapq.heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heapq.heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u].items():
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heapq.heappush(self.Q, (alt, v))

@mt
def slv(N, LRC):
    g = defaultdict(dict)

    for l, r, c in LRC:
        g[l][r] = c
    
    for i in range(1, N):
        g[i+1][i] = 0

    
    d = D2(g, 1)

    return -1 if d.dist[N] == INF else d.dist[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    prev = {}
    q = []
    d = defaultdict(lambda: INF)
    d[s] = 0
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v in g[u]:
            alt = g[u][v] + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (alt, v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)

    for l, r, c in LRC:
        g[l][r] = c
    
    for i in range(1, N):
        g[i+1][i] = 0

    
    d = Dijkstra(g, 1)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s, N):
    V = set(range(1, N+1))

    d = {}
    prev = {}
    q = []
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v in g[u]:
            alt = g[u][v] + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (alt, v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)

    for l, r, c in LRC:
        g[l][r] = c
    
    for i in range(1, N):
        g[i+1][i] = 0

    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s, N):
    V = set(range(1, N+1))

    d = {}
    prev = {}
    q = []
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v in g[u]:
            alt = g[u][v] + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(1, N):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
        if not (r in g and l in g[r]):
            g[r][l] = c
    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s, N):
    V = set(range(1, N+1))

    d = {}
    prev = {}
    q = []
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(1, N):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
        if not (r in g and l in g[r]):
            g[r][l] = c
    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 10.0**100


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s, N):
    V = set(range(1, N+1))

    d = {}
    prev = {}
    q = []
    done = set()
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(1, N):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
        if not (r in g and l in g[r]):
            g[r][l] = c
    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 10.0**100


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s, N):
    V = set(range(1, N+1))

    d = {}
    prev = {}
    q = []
    done = set()
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(1, N):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s, N):
    V = set(range(1, N+1))

    d = {}
    prev = {}
    q = []
    done = set()
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(1, N):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    d = {}
    prev = {}
    q = []
    done = set()
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(1, N):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
    
    d = Dijkstra(g, 1)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()