Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    return d


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, N, E)

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


Fixed submission:
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()

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


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heappush(q, e)
    while q:
        minedge = heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heappush(q, [e[0]+d[v], e[1]])
    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, N, E)

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


if __name__ == '__main__':
    main()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    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, N, E)

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


if __name__ == '__main__':
    main()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
input = sys.stdin.readline


# ダイクストラ法. O(|E|log|V|)
# 頂点数 n, *負の辺が無い* グラフで、頂点 s から各頂点への最短距離を求める (存在しないときはinf)
# 隣接リスト edge[i]: 頂点 i から [cost, dst] のリスト (heapq のため cost が先)
# 辺 i,j w が与えられたとき edge[i], edge[j] とも必要な点に注意
def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    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, N, E)

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


if __name__ == '__main__':
    main()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [float("inf")]*N
    dp[0] = 0
    for (s, t, c) in A:
        for j in range(s, t+1):
            dp[j-1] = min(dp[j-1], dp[s-1] + c)
    ans = dp[N-1]
#    print(dp)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [[float("inf")]*N for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(N+1):
            if j-1 < s or j-1 >= t:
                dp[i+1][j-1] = dp[i][j-1]
                if j-1 >= t and dp[i+1][j-1] == float("inf"):
                    break
            else:
                dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
#    for x in dp:
#        print(x)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [[float("inf")]*N for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(N+1):
            if j-1 < s or j-1 >= t:
                dp[i+1][j-1] = dp[i][j-1]
            else:
                dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
#    for x in dp:
#        print(x)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
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()