Buggy python submission (verdict: Time Limit Exceeded):
def main():
    # 入力
    n, m, r = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    # グラフ
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in abc]

    # 逆辺
    g2 = [[] for _ in [0]*n]
    [g2[b-1].append([a-1, c]) for a, b, c in abc]

    # 前処理用のDFS
    def remove_edge(graph, start):
        q = [start]
        memo = [True for _ in range(n)]
        memo[start] = False
        while q:
            qq = q.pop()
            for i, j in graph[qq]:
                if memo[i]:
                    q.append(i)
                    memo[i] = False
        return {i for i, j in enumerate(memo) if j == True}

    # 前処理
    rmv = remove_edge(g, 0) | remove_edge(g2, n-1)
    for i in rmv:
        g[i] = []
    for i in range(n):
        for j in g[i]:
            if j[0] in rmv:
                g[i].remove(j)

    # ベルマンフォード
    dist = [-10**15 for _ in [0]*n]
    dist[0] = 0

    for k in range(n):
        for p in range(n):
            for i, j in g[p]:
                dist[i] = max(dist[i], dist[p]+j-r)
        if k == n-2:
            d1 = [t for t in dist]
        if k == n-1:
            d2 = [t for t in dist]

    # 1からでもnの間に負の閉路があるときは-1
    if d1 == d2:
        print(max(d1[-1], 0))
    else:
        print(-1)
main()


Fixed submission:
#入力
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
#グラフ
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]
#逆辺
g2=[[] for _ in [0]*n]
[g2[b-1].append([a-1,c]) for a,b,c in abc]

#ベルマンフォード
dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for k in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j-r)
    if k==n-2:
        d1=[t for t in dist]
    if k==n-1:
        d2=[t for t in dist]
    
#負の経路上の頂点の一覧
loop=set()
for i in range(n):
    if d1[i]!=d2[i]:
        loop.add(i)    
ans=max(d2[n-1],0)

#1からの到達可能地点
q=[0]
memo=[True for _ in range(n)]
memo[0]=False
while q:
    qq=q.pop()
    for i,j in g[qq]:
        if memo[i]:
            q.append(i)
            memo[i]=False
            
#nからの逆辺による到達可能地点
q=[n-1]
memo2=[True for _ in range(n)]
memo2[n-1]=False
while q:
    qq=q.pop()
    for i,j in g2[qq]:
        if memo2[i]:
            q.append(i)
            memo2[i]=False
            
#1からでもnからでも行ける点でかつ負の閉路に入っているものがあるときは-1
for i in loop:
    if memo[i]==False and memo2[i]==False:
        ans=-1
        
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    # 入力
    n, m, r = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    # グラフ
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in abc]

    # 逆辺
    g2 = [[] for _ in [0]*n]
    [g2[b-1].append([a-1, c]) for a, b, c in abc]

    # 前処理用のDFS
    def remove_edge(graph, start):
        q = [start]
        memo = [True for _ in range(n)]
        memo[start] = False
        while q:
            qq = q.pop()
            for i, j in graph[qq]:
                if memo[i]:
                    q.append(i)
                    memo[i] = False
        return {i for i, j in enumerate(memo) if j == True}

    # 前処理
    rmv = remove_edge(g, 0) | remove_edge(g2, n-1)
    for i in rmv:
        g[i] = []
    for i in range(n):
        for j in g[i]:
            if j[0] in rmv:
                g[i].remove(j)

    # ベルマンフォード
    dist = [-10**15 for _ in [0]*n]
    dist[0] = 0

    for k in range(n):
        for p in range(n):
            for i, j in g[p]:
                dist[i] = max(dist[i], dist[p]+j-r)
        if k == n-2:
            d1 = [t for t in dist]
        if k == n-1:
            d2 = [t for t in dist]

    # 1からでもnの間に負の閉路があるときは-1
    if d1 == d2:
        print(max(d1[-1], 0))
    else:
        print(-1)
main()

Fixed submission:
#入力
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
#グラフ
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]
#逆辺
g2=[[] for _ in [0]*n]
[g2[b-1].append([a-1,c]) for a,b,c in abc]

#ベルマンフォード
dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for k in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j-r)
    if k==n-2:
        d1=[t for t in dist]
    if k==n-1:
        d2=[t for t in dist]
    
#負の経路上の頂点の一覧
loop=set()
for i in range(n):
    if d1[i]!=d2[i]:
        loop.add(i)    
ans=max(d2[n-1],0)

#1からの到達可能地点
q=[0]
memo=[True for _ in range(n)]
memo[0]=False
while q:
    qq=q.pop()
    for i,j in g[qq]:
        if memo[i]:
            q.append(i)
            memo[i]=False
            
#nからの逆辺による到達可能地点
q=[n-1]
memo2=[True for _ in range(n)]
memo2[n-1]=False
while q:
    qq=q.pop()
    for i,j in g2[qq]:
        if memo2[i]:
            q.append(i)
            memo2[i]=False
            
#1からでもnからでも行ける点でかつ負の閉路に入っているものがあるときは-1
for i in loop:
    if memo[i]==False and memo2[i]==False:
        ans=-1
        
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]

g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[n-1]

if a==b:
    ans=0
    loop=set()
    d=[-10**15 for _ in [0]*n]
    d[0]=0
    q=[[0,1]]
    s=set()
    l=[]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        for q_item in q:
            item,depth=q_item
            if depth<=len(s):
                for _ in range(len(s)-depth+1):
                    rmv=l.pop()
                    s.remove(rmv)
            l.append(item)
            s.add(item)
            for i,dist in g[item]:
                if d[i]<d[item]+dist:
                    if i in s:
                        loop.add(i)
                        continue
                    d[i]=d[item]+dist
                    qq.append([i,depth+1])
          
        c=[False for _ in [0]*n]
        for x in loop:
            if c[x]==True:
                continue
            qqq=[x]
            c[x]=True
            while qqq:
                item=qqq.pop()
                for i,j in g[item]:
                    if c[i]==False:
                        c[i]=True
                        qq.append(i)
        ans=max(ans,d[n-1]-cnt*r)
        q=qq
    print(ans)
else:
    print(-1)

Fixed submission:
#入力
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
#グラフ
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]
#逆辺
g2=[[] for _ in [0]*n]
[g2[b-1].append([a-1,c]) for a,b,c in abc]

#ベルマンフォード
dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for k in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j-r)
    if k==n-2:
        d1=[t for t in dist]
    if k==n-1:
        d2=[t for t in dist]
    
#負の経路上の頂点の一覧
loop=set()
for i in range(n):
    if d1[i]!=d2[i]:
        loop.add(i)    
ans=max(d2[n-1],0)

#1からの到達可能地点
q=[0]
memo=[True for _ in range(n)]
memo[0]=False
while q:
    qq=q.pop()
    for i,j in g[qq]:
        if memo[i]:
            q.append(i)
            memo[i]=False
            
#nからの逆辺による到達可能地点
q=[n-1]
memo2=[True for _ in range(n)]
memo2[n-1]=False
while q:
    qq=q.pop()
    for i,j in g2[qq]:
        if memo2[i]:
            q.append(i)
            memo2[i]=False
            
#1からでもnからでも行ける点でかつ負の閉路に入っているものがあるときは-1
for i in loop:
    if memo[i]==False and memo2[i]==False:
        ans=-1
        
print(ans)