Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)

for i in range(1, n):
    g[i][i-1] = 0


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in enumerate(g[u]):
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**10 else -1)


Fixed submission:
from heapq import heappop, heappush

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

g = [[] for __ in range(n)]

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

for i in range(1, n):
    g[i].append((i-1, 0))


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in g[u]:
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**18 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)

for i in range(1, n):
    g[i][i-1] = 0


d = [10**13] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in enumerate(g[u]):
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**10 else -1)


Fixed submission:
from heapq import heappop, heappush

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

g = [[] for __ in range(n)]

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

for i in range(1, n):
    g[i].append((i-1, 0))


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in g[u]:
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**18 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)

for i in range(1, n):
    g[i][i-1] = 0


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


d = dijkstra(0, n, g)
print(d[n-1] if d[n-1] != 10**10 else -1)

Fixed submission:
from heapq import heappop, heappush

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

g = [[] for __ in range(n)]

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

for i in range(1, n):
    g[i].append((i-1, 0))


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in g[u]:
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**18 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

flag = [0]*n  # flag[i]:i←i+1 に0のパスがある(0<=i<=n-1)

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)
    flag[l-1] += 1
    flag[r-1] += -1

for i in range(1, n):
    flag[i] += flag[i-1]
    if flag[i-1] != 0:
        g[i][i-1] = 0


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


d = dijkstra(0, n, g)
print(d[n-1] if d[n-1] != 10**10 else -1)


Fixed submission:
from heapq import heappop, heappush

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

g = [[] for __ in range(n)]

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

for i in range(1, n):
    g[i].append((i-1, 0))


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in g[u]:
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**18 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

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


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


d = dijkstra(0, n, g)
print(d[n-1] if d[n-1] != 10**10 else -1)


Fixed submission:
from heapq import heappop, heappush

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

g = [[] for __ in range(n)]

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

for i in range(1, n):
    g[i].append((i-1, 0))


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in g[u]:
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**18 else -1)