Problem p03722 (python)

Fixed submission:
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N

#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        if count == N:
            # print ('B')
            path = restore(N)
            # print (prev)
            # print (path)
            update = False
            for i in range(M): #無向グラフのときは辺は実質的には2倍
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if e[1] in path:
                        return False
                    update = True
                    prev[e[1]] = e[0]
            return True

        count += 1
        # print ('A')
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                prev[e[1]] = e[0]
        if not update:
            return True

#呼び出しスタート地点を入れる
if shortest_path(1):
    print (-d[N - 1])
else:
    print ('inf')

# print (d)

Buggy submission (verdict: Runtime Error):
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N

#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        if count == N:
            # print ('B')
            path = restore(N)
            # print (path)
            update = False
            for i in range(M): #無向グラフのときは辺は実質的には2倍
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if e[i] in path:
                        return False
                    update = True
                    prev[e[1]] = e[0]
            return True

        count += 1
        # print ('A')
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                prev[e[1]] = e[0]
        if not update:
            return True

#呼び出しスタート地点を入れる
if shortest_path(1):
    print (-d[N - 1])
else:
    print ('inf')

# print (d)

Buggy submission (verdict: Runtime Error):
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N

#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        if count == N:
            # print ('B')
            path = set(restore(N))
            # print (path)
            update = False
            for i in range(M): #無向グラフのときは辺は実質的には2倍
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if e[i] in path:
                        return False
                    update = True
                    prev[e[1]] = e[0]
            return True

        count += 1
        # print ('A')
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                prev[e[1]] = e[0]
        if not update:
            return True

#呼び出しスタート地点を入れる
if shortest_path(1):
    print (-d[N - 1])
else:
    print ('inf')

# print (d)