Problem:
 Score : 500 points    Problem Statement There is a directed graph with N vertices numbered 1 to N and M edges.
The i -th edge is directed from Vertex A_i to Vertex B_i , and there are C_i coins placed along that edge.
Additionally, there is a button on Vertex N .  We will play a game on this graph.
You start the game on Vertex 1 with zero coins, and head for Vertex N by traversing the edges while collecting coins.
It takes one minute to traverse an edge, and you can collect the coins placed along the edge each time you traverse it.
As usual in games, even if you traverse an edge once and collect the coins, the same number of coins will reappear next time you traverse that edge, which you can collect again.  When you reach Vertex N , you can end the game by pressing the button. (You can also choose to leave Vertex N without pressing the button and continue traveling.)
However, when you end the game, you will be asked to pay T \times P coins, where T is the number of minutes elapsed since the start of the game. If you have less than T \times P coins, you will have to pay all of your coins instead.  Your score will be the number of coins you have after this payment.
Determine if there exists a maximum value of the score that can be obtained. If the answer is yes, find that maximum value.      Constraints  2 \leq N \leq 2500  1 \leq M \leq 5000  1 \leq A_i, B_i \leq N  1 \leq C_i \leq 10^5  0 \leq P \leq 10^5  All values in input are integers.  Vertex N can be reached from Vertex 1 .         Input Input is given from Standard Input in the following format:  N  M  P  A_1  B_1  C_1  :  A_M  B_M  C_M       Output If there exists a maximum value of the score that can be obtained, print that maximum value; otherwise, print -1 .        Sample Input 1 3 3 10
1 2 20
2 3 30
1 3 45      Sample Output 1 35   There are two ways to travel from Vertex 1 to Vertex 3 :   Vertex 1 \rightarrow 2 \rightarrow 3 : You collect 20 + 30 = 50 coins on the way. After two minutes from the start of the game, you press the button, pay 2 \times 10 = 20 coins, and you have 50 - 20 = 30 coins left.  Vertex 1 \rightarrow 2 : You collect 45 coins on the way. After one minute from the start of the game, you press the button, pay 1 \times 10 = 10 coins, and you have 45 - 10 = 35 coins left.   Thus, the maximum score that can be obtained is 35 .       Sample Input 2 2 2 10
1 2 100
2 2 100      Sample Output 2 -1   The edge extending from Vertex 1 takes you to Vertex 2 . If you then traverse the edge extending from Vertex 2 to itself t times and press the button, your score will be 90 + 90t . Thus, you can infinitely increase your score, which means there is no maximum value of the score that can be obtained.       Sample Input 3 4 5 10
1 2 1
1 4 1
3 4 1
2 2 100
3 3 100      Sample Output 3 0   There is no way to travel from Vertex 1 to Vertex 4 other than traversing the edge leading from Vertex 1 to Vertex 4 directly. You will pick up one coin along this edge, but after being asked to paying 10 coins, your score will be 0 .  Note that you can collect an infinite number of coins if you traverse the edge leading from Vertex 1 to Vertex 2 , but this is pointless since you can no longer reach Vertex 4 and end the game.

Solution (Python):
import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford, connected_components
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

input = sys.stdin.buffer.readline
epsilon = 2 ** -26 

N, M, P = map(int, input().split())
graph = np.zeros((N, N), np.float64)
for _ in range(M):
    a, b, c = map(int, input().split())
    if graph[a-1][b-1] == 0:
        if -c+P == 0:
            graph[a-1][b-1] = epsilon
        else:
            graph[a-1][b-1] = -c+P
    elif graph[a-1][b-1] > -c+P:
        if -c+P == 0:
            graph[a-1][b-1] = epsilon
        else:
            graph[a-1][b-1] = -c+P

tmp = graph[-1, 0]

graph[-1, 0] = epsilon
_, labels = connected_components(graph, connection = "strong")
mask = (labels == labels[0])


graph[-1, 0] = tmp
graph = graph[mask, :][:, mask]

try:
    ans = bellman_ford(graph, directed = True, indices = 0)[-1]
    ans = max(0, int(round(-ans)))
except NegativeCycleError:
    ans = -1

print(ans)

Solution (Python):
from collections import deque 
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m,p = inm()
dst = [{} for i in range(n+1)]
src = [{} for i in range(n+1)]
es = []
for i in range(m):
    a,b,c = inm()
    dst[a][b] = src[b][a] = p-c
    es.append((a,b,p-c))

rf1 = [False]*(n+1)
rf1[1] = True
q = deque([1])
while len(q)>0:
    x = q.popleft()
    for y in dst[x]:
        if not rf1[y]:
            rf1[y] = True
            q.append(y)

rtn = [False]*(n+1)
rtn[n] = True
q = deque([n])
while len(q)>0:
    x = q.popleft()
    for y in src[x]:
        if not rtn[y]:
            rtn[y] = True
            q.append(y)

ddprint(rf1)
ddprint(rtn)

use = [rf1[i] and rtn[i] for i in range(n+1)]

es = [z for z in es if use[z[0]] and use[z[1]]]
ddprint(es)

dp = [BIG]*(n+1)
dp[1] = 0
for i in range(n):
    ddprint(dp)
    for a,b,c in es:
        if dp[b] > dp[a]+c:
            dp[b] = dp[a]+c
            if i==n-1:
                print(-1)
                exit()

print(max(0,-dp[n]))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, m, p = LI()
abc = [LI() for _ in range(m)]
edges = [[] for _ in range(n)]
inv_edges = [[] for _ in range(n)]
for a, b, c in abc:
    edges[a-1].append((b-1, c))
    inv_edges[b-1].append(a-1)

visited = [False] * n
stack = [n-1]
while stack:
    v = stack.pop()
    visited[v] = True
    for u in inv_edges[v]:
        if visited[u]:
            continue
        stack.append(u)

dp = [-float('inf')] * n
dp[0] = 0
tmp = -1
for _ in range(n+1):
    flag = False
    for v in range(n):
        score = dp[v]
        for u, c in edges[v]:
            if dp[u] < score + c - p and visited[u]:
                dp[u] = score + c - p
                flag = True
if flag:
    print(-1)
else:
    print(max(0, dp[n-1]))

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    
    N, M, P = map(int, input().split())
    
    
    
    def tree_init(N):
        ws=[]
        edgelist = [[] for _ in range(N)]
        for a, b, w in [map(int, input().split()) for i in range(M)]:
            edgelist[a-1].append((-w,b-1))
            ws.append(-w)
        return edgelist,ws


    edge,ws=tree_init(N)



    inf=10**14
    def bellman_ford(N,s,edge):
        inf=10**14
        d=[inf]*N
        upper=[set() for _ in range(N)]
        d[s]=0
        count=0
        for _ in range(N):
            update=False
            for e in range(N):
                if d[e]==inf:
                    continue
                for nd,ne in edge[e]:
                    x=max(-inf,d[e]+nd+P)
                    if x<d[ne]:
                        d[ne]=x
                        update=True
            if update==False: break

        for _ in range(N):
            update=False
            for e in range(N):
                if d[e]==inf:
                    continue
                for nd,ne in edge[e]:
                    x=max(-inf,d[e]+nd+P)
                    if x<d[ne]:
                        d[ne]=-inf
                        update=True
            if update==False: break

        return d

    visited=bellman_ford(N,0,edge)
    if visited[-1]==-inf:
        print(-1)
        return
    print(max(-visited[-1],0))
    


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR_(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')


def solve():
    n, m, p = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        c += 1
        edg[a].append((b, c))
    dp = [-inf] * n
    dp[0] = 0
    for j in range(n):
        for i in range(n):
            score = dp[i]
            for e, s in edg[i]:
                if dp[e] < score + s - p:
                    dp[e] = score + s - p
    ans = dp[:]
    for j in range(n):
        for i in range(n):
            score = dp[i]
            for e, s in edg[i]:
                if dp[e] < score + s - p:
                    dp[e] = inf
    if ans[-1] != dp[-1]:
        print(-1)
    else:
        print(abs(max(ans[-1],0)))
    return



if __name__ == '__main__':
    solve()

Solution (Python):
from collections import defaultdict, deque
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M, P = map(int, input().split())
d = defaultdict(list)
e = defaultdict(list)
cd = defaultdict(list)
l = []

for _ in range(M):
    a, b, c = map(int, input().split())
    cd[a].append((b, P-c))
    d[a].append(b)
    e[b].append(a)

def check_visited(d, start):
    visited = [False]*(N+1)
    visited[start] = True
    q = deque([start])
    while q:
        s = q.popleft()
        for t in d[s]:
            if visited[t]:continue
            visited[t] = True
            q.append(t)
    
    s = set()
    for i in range(1, N+1):
        if visited[i]:
            s.add(i)
    return s

def shortest_path(s):
    INF = 10**18
    dist = [float("inf")]*(N+1)
    dist[s] = 0

    for i in range(N):
        for a, b, c in l:
            if dist[b]>dist[a]+c:
                dist[b] = dist[a]+c
                if i==N-1:
                    return dist, True
    return dist, False

add_l = check_visited(d, 1)&check_visited(e, N)
for a in add_l:
    for b, c in cd[a]:
        l.append((a, b, c))
d1, neg = shortest_path(1)
print(-1 if neg else max(0, -d1[N]))

Solution (Python):
from collections import defaultdict, deque
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M, P = map(int, input().split())
d = defaultdict(list)
e = defaultdict(list)
cd = defaultdict(list)
l = []

for _ in range(M):
    a, b, c = map(int, input().split())
    cd[a].append((b, P-c))
    d[a].append(b)
    e[b].append(a)

def check_visited(d, start):
    visited = [False]*(N+1)
    visited[start] = True
    q = deque([start])
    while q:
        s = q.popleft()
        for t in d[s]:
            if visited[t]:continue
            visited[t] = True
            q.append(t)
    
    s = set()
    for i in range(1, N+1):
        if visited[i]:
            s.add(i)
    return s

def shortest_path(s):
    INF = 10**18
    dist = [float("inf")]*(N+1)
    dist[s] = 0

    for i in range(N):
        for a, b, c in l:
            if dist[b]>dist[a]+c:
                dist[b] = dist[a]+c
                if i==N-1:
                    return dist, True
    return dist, False

add_l = check_visited(d, 1)&check_visited(e, N)
for a in add_l:
    for b, c in cd[a]:
        l.append((a, b, c))
d1, neg = shortest_path(1)
if neg:
    print(-1)
elif d1[N]<0:
    print(-d1[N])
else:
    print(0)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 10

class edge:
    def __init__(self, fr, to, cost): self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M, P = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -(c-P)))

    d = [INF] * N
    d[0] = 0
    for i in range(N-1):
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
    n = [False] * N
    for i in range(N):
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                n[e.to] = True
            if n[e.fr] == True: n[e.to] = True
    print(-1 if n[N-1] else max(0, -d[N-1]))

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M,P = map(int,readline().split())
ABC = np.array(read().split(),np.int64)

A = ABC[::3]
B = ABC[1::3]
C = ABC[2::3]

C = P-C



INF = 10**18
dist = np.full(N+1,INF,np.int64)
dist[1] = 0
for T in range(N+N+10):
    x = dist[A] + C
    update = (dist[B] > x) & (x < INF//2)
    b = B[update]; x = x[update]
    if T > N:
        dist[b] = -INF
    else:
        ind = x.argsort(); x = x[ind][::-1]; b=b[ind][::-1]
        dist[b] = x

answer = -dist[N]
if answer < 0:
    answer = 0
elif answer == INF:
    answer = -1
print(answer)

Solution (Python):
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
import sys
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())

    edges = []
    routes = [[] for _ in range(n)]
    rev_routes = [[] for _ in range(n)]

    def get_reachable_nodes(start, routes):
        seen = {start}
        todo = []
        for to in routes[start]:
            todo.append(to)
            seen.add(to)

        while todo:
            node = todo.pop()
            for to in routes[node]:
                if to in seen:
                    continue
                todo.append(to)
                seen.add(to)
        return seen

    for _ in range(m):
        node1, node2, value = map(int, input().split())
        node1, node2, value = node1 - 1, node2 - 1, value - p
        edges.append([node1, node2, value])
        routes[node1].append(node2)
        rev_routes[node2].append(node1)

    from_start = get_reachable_nodes(0, routes)
    if n-1 not in from_start:
        print(-1)
        return

    to_goal = get_reachable_nodes(n-1, rev_routes)

    from_start_to_goal = from_start & to_goal

    temp_dict = dict()

    for row, col, value in edges:
        if {row, col} <= from_start_to_goal:
            if not (row, col) in temp_dict:
                temp_dict[(row, col)] = -value
            else:
                temp_dict[(row, col)] = min(-value, temp_dict[(row, col)])

    values = []
    rows = []
    cols = []

    for (row, col), minus_value in temp_dict.items():
        values.append(minus_value)
        rows.append(row)
        cols.append(col)

    graph = coo_matrix((values, (rows, cols)), shape=(n, n))
    try:
        bf = bellman_ford(graph, indices=[0])
        print(max(0, -int(bf[0][n - 1])))
    except NegativeCycleError:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix
from collections import defaultdict

n, m, p = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
INF = 10 ** 9

fwd = [[] for _ in range(n + 1)]
rev = [[] for _ in range(n + 1)]

for a, b, c in abc:
    fwd[a].append(b)
    rev[b].append(a)


def dfs(s, adj):
    stack = [s]
    arrived = [False] * (n + 1)
    arrived[s] = True
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if not arrived[v]:
                arrived[v] = True
                stack.append(v)

    return arrived


can_go_fwd = dfs(1, fwd)
can_go_rev = dfs(n, rev)

data = defaultdict(lambda: INF)
for a, b, c in abc:
    if can_go_fwd[a] and can_go_rev[b]:
        data[(a, b)] = min(data[(a, b)], p - c)

row = []
col = []
cost = []
for (a, b), c in data.items():
    row.append(a)
    col.append(b)
    cost.append(c)

g = csr_matrix((cost, (row, col)), shape=(n + 1, n + 1))

try:
    dist = bellman_ford(g, indices=[1]).astype(int)
    ans = max(0, -dist[0][n])
    print(ans)
except NegativeCycleError:
    print(-1)

Solution (Python):
class Edge:
  def __init__(self, starting_point, arrival_point, cost):
    self.starting_point = starting_point
    self.arrival_point = arrival_point
    self.cost = cost

def solve():
  N, M, P = map(int, input().split())
  edges = []
  INF = float('inf')
  dist = [INF for _ in range(N + 10)]
  dist[1] = 0
  for i in range(M):
    a, b, c = map(int, input().split())
    e = Edge(a, b, -c + P)
    edges.append(e)
  for i in range(2 * N):
    for e in edges:
      if dist[e.arrival_point] > e.cost + dist[e.starting_point]:
        dist[e.arrival_point] = e.cost + dist[e.starting_point]
        if i == N - 1:
          dist[e.arrival_point] = -INF
  if dist[N] != -INF:
    return max(-dist[N], 0)
  else:
    return -1
print(solve())

Solution (Python):
def resolve():
    def BF(s, n, edge, inf=float("inf")):
        d = [inf for i in range(n)]
        d[s] = 0
        for i in range(n * 2):
            for before, after, dist in edge:
                if before != inf and d[before] + dist < d[after]:
                    if i < n:
                        d[after] = d[before] + dist
                    else:
                        d[after] = -inf
        return d
    n, m, p = map(int, input().split())
    inf = float("inf")
    edge = [list(map(int, input().split())) for _ in range(m)]
    edge = [[x - 1, y - 1, p - z] for x, y, z in edge]
    ans = -BF(0, n, edge, inf)[-1]
    print(max(0, ans) if ans < inf else -1)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys

input = sys.stdin.buffer.readline

n, m, p = map(int, input().split())
graph = [[] for _ in range(n + 1)]
revgraph = [[] for _ in range(n + 1)]
loop = [False] * (n + 1)
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c - p))
    graph[a].append((b, c - p))
    revgraph[b].append((a, c - p))
is_route = [False] * (n + 1)

start = 1

stack = [start]
while stack:
    v = stack.pop()
    is_route[v] = True
    for u, c in graph[v]:
        if is_route[u]:
            continue
        stack.append(u)
is_revroute = [False] * (n + 1)

goal = n
stack = [goal]
while stack:
    v = stack.pop()
    is_revroute[v] = True
    for u, c in revgraph[v]:
        if is_revroute[u]:
            continue
        stack.append(u)


def check(v):
    return is_route[v] and is_revroute[v]




dist = [-(10 ** 10)] * (n + 1)
start = 1
dist[start] = 0
cnt = 0
update = True
used = set([start])
while update:
    cnt += 1
    update = False
    for fr, to, co in edges:
        if check(fr) and check(to):
            if dist[fr] != -(10 ** 10) and dist[to] < dist[fr] + co:
                dist[to] = dist[fr] + co
                update = True
    if not update:
        break
    if cnt > n:
        print(-1)
        exit()
print(max(0, dist[n]) if dist[n] != -(10 ** 10) else -1)

Solution (Python):
import collections
import heapq
import copy
n,m,p = map(int,raw_input().split(' '))

adj = collections.defaultdict(list)
def f(e,p):
	u,v,w = e
	return (u,v,p-w)

edges = [f(map(int, raw_input().split()), p) for _ in range(m) ]

fa = collections.defaultdict(list)
ba = collections.defaultdict(list)
for u,v,_ in edges:
	fa[u].append(v)
	ba[v].append(u)
def dfs(u,adj,vis):
	stack = collections.deque([u])
	while(stack):
		uu = stack.pop()
		vis.add(uu)

		for v in adj[uu]:
			if v not in vis:
				vis.add(v)
				stack.append(v)
va = set([1])
dfs(1, fa, va)

vb = set([n])
dfs(n, ba, vb)

h = {u: (+float('inf') if u > 1 else 0) for u in range(1, n + 1)}

for _ in range(n-1):
	for u,v,w in edges: h[v] = min(h[v], h[u] + w)

fnc = False
for u,v,w in edges: 
	if v in va and v in vb and h[v] > h[u] + w:
		fnc = True
		break
print max(0,-h[n]) if (not(fnc) and h[n] != +float('inf')) else -1

Solution (Python):
import sys
input = sys.stdin.readline

INF = 10**18

N, M, P = map(int, input().split())
G = []
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
updated = [False]*N
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if (D[fr] != -INF and D[fr]+cost > D[to]) or updated[fr]:
            updated[to] = True
if updated[N-1]:
    print(-1)
elif D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Solution (Python):
import sys
input = sys.stdin.readline

INF = 10**18

N, M, P = map(int, input().split())
G = []
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = INF
            if to == N-1:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Solution (Python):
INF = 10**18

N, M, P = map(int, input().split())
G = []
G1 = [[] for i in range(N)]
G2 = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
tmpAns = D[N-1]
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = INF
            if to == N-1 and D[to] != tmpAns:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18

def dfs1(cur):
    for to in G1[cur]:
        if done1[to]: continue
        done1[to] = True
        dfs1(to)

def dfs2(cur):
    for to in G2[cur]:
        if done2[to]: continue
        done2[to] = True
        dfs2(to)

N, M, P = map(int, input().split())
G = []
G1 = [[] for i in range(N)]
G2 = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
    G1[a].append(b)
    G2[b].append(a)
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
done1 = [False]*N
done1[0] = True
dfs1(0)
done2 = [False]*N
done2[N-1] = True
dfs2(N-1)
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
            if done1[to] and done2[to]:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


from collections import defaultdict

def BellmanFord(g, s, N):
    dist = [INF] * (N+1)
    dist[s] = 0
    for i in range(N):
        for u in range(1, N+1):
            if dist[u] == INF:
                continue
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    dist[v] = dist[u] + g[u][v]
    for i in range(N//2):
        for u in range(1, N+1):
            if dist[u] == INF:
                continue
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    if dist[v] != INF:
                        dist[v] = -INF
    return dist


@mt
def slv(N, M, P, ABC):
    g = defaultdict(dict)
    for a, b, c in ABC:
        if a in g and b in g[a]:
            g[a][b] = min(g[a][b], -(c - P))
        else:
            g[a][b] = -(c - P)

    d = BellmanFord(g, 1, N)
    if -d[N] >= INF:
        return -1
    return max(0, -d[N])





def main():
    N, M, P = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    print(slv(N, M, P, ABC))


if __name__ == '__main__':
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    start = time.time()
    n,m,p = LI()
    abc = [LI() for _ in range(m)]
    er = collections.defaultdict(set)
    err = collections.defaultdict(set)
    for a,b,c in abc:
        er[b].add(a)
        err[a].add(b)

    v = set([n])
    q = [n]
    qi = 0
    while len(q) > qi:
        t = q[qi]
        qi += 1
        for b in er[t]:
            if b not in v:
                v.add(b)
                q.append(b)

    u = set([1])
    q = [1]
    qi = 0
    while len(q) > qi:
        t = q[qi]
        qi += 1
        for b in err[t]:
            if b not in u:
                u.add(b)
                q.append(b)

    v &= u

    e = collections.defaultdict(list)
    for a,b,c in abc:
        if a not in v or b not in v:
            continue
        e[a].append((b,c-p))

    en = len(e)
    km = sum(map(lambda x: x[2], abc))
    def search(s):
        d = collections.defaultdict(lambda: -inf)
        vc = collections.defaultdict(int)
        q = []
        d[s] = 0
        heapq.heappush(q, (0, s))
        ttt = 0
        while len(q):
            ttt += 1
            if ttt % 1024 == 0:
                if time.time() - start > 1.5:
                    return
            mk, u = heapq.heappop(q)
            k = -mk
            if d[u] > k:
                continue
            if k > km or vc[u] > en:
                return
            vc[u] += 1

            for uv, ud in e[u]:
                vd = k + ud
                if d[uv] < vd:
                    d[uv] = vd
                    heapq.heappush(q, (-vd, uv))

        return d

    d = search(1)
    if d is None:
        return -1
    return max(0, d[n])

print(main())

Solution (Python):
def bellman_ford(s, n, G):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    V = [[] for _ in range(n)]
    dic = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        if (a-1, b-1) in dic:
            if dic[(a-1, b-1)] > -c+p:
                dic[(a-1, b-1)] = -c+p
        else:
            dic[(a-1, b-1)] = -c+p
    for v in dic.keys():
        G.append([v[0], v[1], dic[v]])
        U[v[1]].append(v[0])
        V[v[0]].append(v[1])
    st1 = set()
    st1.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st1:
                q.append(v)
                st1.add(v)
    st2 = set()
    st2.add(0)
    q = [0]
    while len(q) > 0:
        t = q.pop(-1)
        for v in V[t]:
            if not v in st2:
                q.append(v)
                st2.add(v)
    st = st1 & st2
    eg = []
    for v in G:
        if v[0] in st and v[1] in st:
            eg.append(v)
    ans = bellman_ford(0, n, eg)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

if __name__ == "__main__":
    main()