Buggy python submission (verdict: Runtime Error):

"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

N,M,P = map(int,input().split())

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))


Fixed submission:

"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

N,M,P = map(int,input().split())

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

N,M,P = map(int,input().split())

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b] or crash[now]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                flag[b] = flag[now].copy()

                for j in range(N):

                    flag[b][j] = flag[now][j]
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                flag[b] = flag[now].copy()
                    
                flag[b][b] = True

                q.append(b)

            else:

                if not crash[b]:
                    crash[b] = crash[now]
                    q.append(b)
                

    cnt += 1

    if cnt > M*N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    


Fixed submission:

"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

N,M,P = map(int,input().split())

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

N,M,P = map(int,input().split())

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b] or crash[now]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                flag[b] = flag[now].copy()

                for j in range(N):

                    flag[b][j] = flag[now][j]
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                flag[b] = flag[now].copy()
                    
                flag[b][b] = True

                q.append(b)

    cnt += 1

    if cnt > M*N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    


Fixed submission:

"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

N,M,P = map(int,input().split())

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

N,M,P = map(int,input().split())

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                for j in range(N):

                    flag[b][j] = flag[now][j]
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                for j in range(N):

                    flag[b][j] = flag[now][j]
                    
                flag[b][b] = True

                q.append(b)

    cnt += 1

    if cnt > M * N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    


Fixed submission:

"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

N,M,P = map(int,input().split())

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

N,M,P = map(int,input().split())

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                flag[b] = flag[now].copy()
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                flag[b] = flag[now].copy()
                flag[b][b] = True

                q.append(b)

    cnt += 1

    if cnt > M * N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    

Fixed submission:

"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

N,M,P = map(int,input().split())

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))