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):
from collections import deque
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []
        self.to = [[] for _ in [0]*self.N]
        self.rev = [[] for _ in range(self.N)]

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
            self.to[u].append(v)
            self.rev[v].append(u)
        else:
            self.edges.append([u, v, d])
            self.to[u].append(v)
            self.rev[v].append(u)

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def check_reachable(self, start, to=True):
        if to:
            edges = self.to
        else:
            edges = self.rev
        visited = [0 for _ in range(self.N)]
        visited[start] = 1
        reachable = set()
        dq = deque([start])
        popleft, append = dq.popleft, dq.append

        while dq:
            current = popleft()
            reachable.add(current)
            for dest in edges[current]:
                if not visited[dest]:
                    visited[dest] = 1
                    append(dest)

        return reachable

    def BellmanFord_negative_bool(self, start, numNodes):
        
        d = [float('inf') for _ in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True, d
        return False, d


N, M, P = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -(c-P), True)

v_set = graph.check_reachable(0) & graph.check_reachable(N-1, False)
graph.edges = [edge for edge in graph.edges if edge[0] in v_set and edge[1] in v_set]
hasNegatibeCycle, dists = graph.BellmanFord_negative_bool(0, N)
if hasNegatibeCycle:
    print(-1)
else:
    print(max(0, -dists[-1]))

Solution (Python):
from collections import deque


def bellman_ford(start: int, goal: int, graph: list) -> list:
    '''bellman-ford法: 始点startから終点goalへの最小コストを求める
    重み付きグラフgraphは隣接リストで与えられる
    辺のコストは負でも良い
    負閉路検出: 始点startから終点goal上のパスに負閉路があるときは[-1]を返す
    計算量: O(|E||V|)
    '''
    INF = float("inf")
    n = len(graph)

    
    is_reachable = [False] * n
    is_reachable[start] = True
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, _ in graph[pos]:
            if is_reachable[next_pos]:
                continue
            is_reachable[next_pos] = True
            q.append(next_pos)

    
    reverse_graph = [[] for i in range(n)]
    for pos, edge in enumerate(graph):
        for next_pos, cost in edge:
            reverse_graph[next_pos].append((pos, cost))

    is_rev_reachable = [False] * n
    is_rev_reachable[goal] = True
    q = deque([goal])
    while q:
        pos = q.popleft()
        for next_pos, _ in reverse_graph[pos]:
            if is_rev_reachable[next_pos]:
                continue
            is_rev_reachable[next_pos] = True
            q.append(next_pos)            

    need = [False] * n
    for i in range(n):
        need[i] = is_reachable[i] and is_rev_reachable[i]

    distance = [INF] * n
    distance[start] = 0
    for _ in range(n):
        is_updated = False
        for pos, edge in enumerate(graph):
            for next_pos, cost in edge:
                if not need[pos]:
                    continue
                if distance[pos] != INF and distance[pos] + cost < distance[next_pos]:
                    distance[next_pos] = distance[pos] + cost
                    is_updated = True
        if not is_updated:
            return distance[goal]
    
    return -INF


n, m, p = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b, c = info[i]
    graph[a - 1].append((b - 1, -(c - p)))
ans = bellman_ford(0, n-1, graph)
if ans == -float("inf"):
    print(-1)
else:
    print(max(-ans, 0))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def find_negative_loop(s,n,w,es):
  
  
  
  
  
  
  inf = float('inf')
  d = [inf for _ in range(n)]
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != inf and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = (-1)*inf
    if i == n-1:
      temp = d[-1]
  return temp, d[-1]
         

n, w, p = map(int, input().split())
es = []
for i in range(w):
  x, y, z = map(int, input().split())
  es.append([x-1, y-1, (z-p)*(-1)])
  
temp, d = find_negative_loop(0, n, w ,es)
if temp == d:
  print(min(0, d)*(-1))
else:
  print('-1')

Solution (Python):
import sys
import time
from queue import Queue
limit_time = time.time() + 1.70
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = M*(1+len(availables))
while not q.empty():
    if time.time() >= limit_time:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)

Solution (Python):
import sys


def input():
    return sys.stdin.readline()[:-1]


n, m, p = map(int, input().split())
edge0 = []
d = [[] for i in range(n)]
r = [[] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    edge0.append((bi-1,ai-1,-ci+p))
    d[ai-1] += [bi-1]
    r[bi-1] += [ai-1]

p0 = [False for i in range(n)]
p0[0] = True
from collections import deque
q = deque([0])
while len(q)>0:
    x = q.popleft()
    for y in d[x]:
        if not p0[y]:
            p0[y] = True
            q.append(y)
pn = [False for i in range(n)]
pn[n-1] = True
q = deque([n-1])
while len(q) > 0:
    x = q.popleft()
    for y in r[x]:
        if not pn[y] and p0[y]:
            pn[y] = True
            q.append(y)

edge = []
for e in edge0:
    if pn[e[1]] and pn[e[0]]:
        edge += [e]


dist = [float("inf") for i in range(n)]
dist[n-1] = 0
h = False
for i in range(n):
    updated = False
    for e in edge:
        if dist[e[1]] > dist[e[0]] + e[2] and p0[e[1]] and p0[e[0]]:
            dist[e[1]] = dist[e[0]] + e[2]
            updated = True
    if not updated:
        break
else:
    h = True

if h:
    print(-1)
else:
    print(max(0, -dist[0]))

Solution (Python):
import sys
sys.setrecursionlimit(10**4)

inf = float('inf')



def bellmanford(start, end):
    global dist
    dist = [inf] * N
    dist[start] = 0
    
    for _ in range(N-1):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
    
    
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            return False
    return True

def dfs(v, ad):
    visited[v] = True
    for nv in ad[v]:
        if not visited[nv]:
            dfs(nv, ad)

N, M, P = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    C -= P
    C *= -1
    to[A].append(B)
    fr[B].append(A)
    edges.append((A, B, C))

visited = [False] * N

dfs(0, to)
tmp = visited[:]
visited = [False] * N
dfs(N-1, fr)
visited = [a and b for a, b in zip(tmp, visited)]
edges = [(v, nv, w) for v, nv, w in edges if visited[v] and visited[nv]]

flag = bellmanford(0, N-1)
ans = max(-dist[N-1], 0) if flag else -1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

def dfs(i):
	if i in use:
		return 
	use.add(i)
	for e in edges_r[i]:
		dfs(e)

def bf():
	d = [float('inf') for _ in range(n + 1)]
	d[1] = 0
	for _ in range(n):
		f = False
		for e in edges_f:
			if d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				f = True	
		if not f:
			return max(0, -1 * d[n])
	return -1

n, m, p = list(map(int, input().split()))

edges_f = []
edges_r = [[] for i in range(n + 1)]
for _ in range(m):
	a, b, c = list(map(int, input().split()))
	edges_f.append([a, b, -1 * (c - p)])
	edges_r[b].append(a)

use = set()
dfs(n)

edges_f = [e for e in edges_f if e[0] in use and e[1] in use]
print(bf())

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n, m, p = map(int, input().split())
edge = []
edge_inv = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b, -c+p))
    edge_inv[b].append(a)


visited = [0] * n
def dfs(v):
    for u in edge_inv[v]:
        if visited[u] == 0:
            visited[u] = 1
            dfs(u)

visited[n-1] = 1
dfs(n-1)
target_nodes = set([i for i in range(n) if visited[i] == 1])

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))

Solution (Python):
import sys

n, m, p = map(int, sys.stdin.readline().split())

abc = []

rev_edge = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, sys.stdin.readline().split())
	abc.append((a-1, b-1, p-c))
	rev_edge[b-1].append(a-1)

def dfs(e, s):
	v_set = {s, }
	stack = [s]

	while stack:
		v = stack.pop()
		for next_v in e[v]:
			if not next_v in v_set:
				stack.append(next_v)
				v_set.add(next_v)
	return v_set

def bellman_ford(sub_abc, n):
	dist = [float('inf')]*n 
	dist[0] = 0

	for _ in range(n):
		updated = False
		for ele in sub_abc:
			a, b, d = ele
			if dist[a] + d < dist[b]:
				dist[b] = dist[a] + d 
				updated = True
		if not updated:
			break
	else:
		return -1

	return max(-dist[n-1], 0)

use = dfs(rev_edge, n-1)
print(bellman_ford([(a, b, c) for a, b, c in abc if a in use and b in use], n))

Solution (Python):
N, M, P = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

class edge:
   f, t, c = 0, 0, 0

inf = 10 ** 5 * (M + 1)
D = [inf] * N
D[0] = 0
E = [edge() for _ in range(M)]
for i in range(M):
  f, t, c = ABC[i]
  E[i].f = f - 1
  E[i].t = t - 1
  E[i].c = P - c
  
L = [False] * N
L[-1] = True
for i in range(N):
  for j in range(M):
    e = E[j]
    if L[e.t]:
      L[e.f] = True

cnt = N + 1
while True:
  flag = True
  for i in range(M):
    e = E[i]
    if D[e.f] != inf and D[e.t] > D[e.f] + e.c:
      D[e.t] = D[e.f] + e.c
      flag = False
      if cnt == 1:
        if L[e.t]:
          print(-1)
          exit()
  if flag:
    break
  cnt -= 1
  if cnt <= 0:
    break

print(max(0, -D[-1]))

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

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g2[b].append(a)
        g[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    q = queue.Queue()
    q.put(1)
    visit[1] = True
    while (not q.empty()):
        now = q.get()
        for next in g[now]:
            if not visit[next]:
                visit[next] = True
                q.put(next)

    q = queue.Queue()
    q.put(N)
    visit2[N] = True
    while (not q.empty()):
        now = q.get()
        for next in g2[now]:
            if not visit2[next]:
                visit2[next] = True
                q.put(next)

    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = 1000000001
    d = [(-1)*INF for i in range(N+1)]
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def main():
    N, M, P = input([int, 3])
    ABC = input([[int, 3], M])

    
    g = nlist([N + 1], [])
    for a, b, _ in ABC:
        g[b] += [a]
    que, rch = [N], {N}
    while que:
        cur = que.pop()
        for nxt in g[cur]:
            if nxt in rch: continue
            rch |= {nxt}
            que.append(nxt)
    edges = [(a, b, c) for a, b, c in ABC if a in rch and b in rch]

    
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in edges:
            c = -(c - P)
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        
        print(-1)
        return
    print(max(0, -g[N]))
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(12345678)

def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        c = -(c - p)
        edges.append((a, b, c))
        graph[a].append(b)
        rev_graph[b].append(a)

    
    reachable_from_start = [False] * n

    
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(1000000)

def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        c = -(c - p)
        edges.append((a, b, c))
        graph[a].append(b)
        rev_graph[b].append(a)

    
    reachable_from_start = [False] * n

    
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Solution (Python):
import collections
N, M, P = [int(_) for _ in input().split()]
ABC = [[int(_) for _ in input().split()] for _ in range(M)]
cd = collections.defaultdict
Ga = cd(set)
Gb = cd(set)
G = []
ok = cd(int)
for a, b, c in ABC:
    Ga[a].add(b)
    Gb[b].add(a)

for pair in [[1, Ga], [N, Gb]]:
    S = pair
    Gn = pair.pop()
    visited = [0] * (N + 1)
    while S:
        s = S.pop()
        if not visited[s]:
            visited[s] = 1
            ok[s] += 1
            for ns in Gn[s]:
                S += [ns]
for a, b, c in ABC:
    if ok[a] == ok[b] == 2:
        G += [(a, b, P - c)]


def bellman_ford(V, G, i):
    INF = float('inf')
    D = [INF] * V
    D[i] = 0
    for _ in range(V):
        update = False
        for s, t, d in G:
            if D[s] != INF and D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            return D
        if _ == V:
            return False


a = bellman_ford(N + 1, G, 1)
try:
    print(max(-a[-1], 0))
except:
    print(-1)

Solution (Python):
import collections

n, m, p = map(int, input().split())
dist1 = []
edges1 = [[] for _ in range(n)]
edges2 = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dist1.append((a, b, (c - p) * -1))
    edges1[a].append(b)
    edges2[b].append(a)

def dfs(edges, start):
    stack = [start]
    use = {start, }
    while stack:
        x = stack.pop()
        for y in edges[x]:
            if y in use:
                continue
            stack.append(y)
            use.add(y)
    return use


def bellman_ford(dist):
    v = [float('inf')] * n
    v[0] = 0
    for _ in range(n):
        updated = False
        for a, b, c in dist:
            if v[a] + c < v[b]:
                updated = True
                v[b] = v[a] + c
        if not updated:
            return max(0, v[n - 1] * -1)
    return -1

use = dfs(edges1, 0) & dfs(edges2, n - 1)
dist2 = [(a, b, c) for a, b, c in dist1 if a in use and b in use]
print(bellman_ford(dist2))

Solution (Python):
import collections


def bellman_ford(es, n, start):
    infinity = float("inf")
    m = len(es)

    d = [infinity] * (n + 1)
    d[start] = 0

    for _ in range(m):
        updated = False

        for u, v, w in es:
            if d[u] == infinity: continue

            dd = d[u] + w

            if dd < d[v]:
                d[v] = dd
                updated = True

        if not updated: break

    for u, v, w in es:
        if d[u] < infinity and d[u] + w < d[v]:
            return None, True

    return d, False


N, M, P = [int(e) for e in input().split()]

Es = [None] * M

for i in range(M):
    a, b, c = ([int(e) for e in input().split()])
    Es[i] = (a - 1, b - 1, P - c)

q = collections.deque()
q.append(N - 1)

valid = [False] * N
valid[N - 1] = True

while 0 < len(q):
    cur = q.popleft()

    for u, v, _ in Es:
        if cur == v and not valid[u]:
            valid[u] = True
            q.append(u)

es_tmp = []
for e in Es:
    if valid[e[0]] and valid[e[1]]:
        es_tmp.append(e)

Es = es_tmp

distances, le = bellman_ford(Es, N - 1, 0)

if le:
    print(-1)
else:
    print(max(-distances[-1], 0))

Solution (Python):
n, m, p = map(int, input().split())

abc = []

rev_edge = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append((a - 1, b - 1, p - c))
    
    rev_edge[b - 1].append(a - 1)


def dfs(e, s):
    v_set = {s}
    stack = [s]
    while stack:
        v = stack.pop()
        for next_v in e[v]:
            if next_v in v_set:
                continue
            v_set.add(next_v)
            stack.append(next_v)
    return v_set


def bellman_ford(sub_abc, n):
    inf = float("inf")
    dist = [inf] * n
    dist[0] = 0

    for _ in range(n):
        updated = False
        for u, v, d in sub_abc:
            if dist[u] + d < dist[v]:
                dist[v] = dist[u] + d
                updated = True
        if not updated:
            break
    else:
        return -1

    return max(-dist[n - 1], 0)


use = dfs(rev_edge, n - 1)
print(bellman_ford([(a, b, c)
                    for (a, b, c) in abc if a in use and b in use], n))

Solution (Python):
n, m, p = map(int, input().split())

abc = []
edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append((a - 1, b - 1, p - c))
    edge[a - 1].append(b - 1)
    rev_edge[b - 1].append(a - 1)


def dfs(e, s):
    v_set = {s}
    stack = [s]
    while stack:
        v = stack.pop()
        for next_v in e[v]:
            if next_v in v_set:
                continue
            v_set.add(next_v)
            stack.append(next_v)
    return v_set


def bellman_ford(sub_abc, n):
    inf = float("inf")
    dist = [inf] * n
    dist[0] = 0

    for _ in range(n):
        updated = False
        for u, v, d in sub_abc:
            if dist[u] + d < dist[v]:
                dist[v] = dist[u] + d
                updated = True
        if not updated:
            break
    else:
        return -1

    return max(-dist[n - 1], 0)


use = dfs(edge, 0) & dfs(rev_edge, n - 1)
print(bellman_ford([(a, b, c)
                    for (a, b, c) in abc if a in use and b in use], n))

Solution (Python):
N,M,P = map(int,input().split())
abc = []
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    
    edge[b-1].append(a-1)
    abc.append((a-1,b-1,P-c))

def dfs(edge,goal):
    
    used = {goal}
    q = [goal]
    while q:
        v = q.pop()
        for w in edge[v]:
            if w in used:continue
            used.add(w)
            q.append(w)
    
    return used

def bellman_ford(v,s,g,e):

    '''
    v: vertex(頂点)
    s: start.  in this case,0
    g: goal. in this case,n-1
    e: (edge_start,egde_goal,score)
    今回はp-cの最小値を求めていく.
    '''
    inf = 10**10
    
    d = [inf] * v
    
    d[s] = 0
    for _ in range(v):
        flag = False
        for a,b,c in e:
            
            if d[a] == inf:continue
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                flag = True
        if not flag: break
    if flag:
        return -1
    return max(-d[g],0)

vertex = dfs(edge,N-1)
abc_ = [(a,b,c) for a,b,c in abc if a in vertex and b in vertex]
print(bellman_ford(N,0,N-1,abc_))

Solution (Python):
N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)
INF = float("inf")
d = [INF for _ in range(N)]
d[0] = 0
for i in range(2*N):
    for f, t, w in E:
        if d[t] > d[f] + w:
            d[t] = d[f] + w
            if i >= N:
                d[t] = -INF
    if i == N-1:
        dN = d[-1]
if dN != d[-1]:
    print(-1)
elif dN > 0:
    print(0)
else:
    print(-dN)

Solution (Python):
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M,P = inpl()
lines = defaultdict(set)

for _ in range(M):
    a,b,c = inpl()
    a,b = a-1,b-1
    lines[a].add((b,-c+P))


def BellmanFord(Start,Goal):
    Costs=[INF]*N
    Costs[Start] = 0
    
    for i in range(2*N): 
        
        for s in range(N):
            
            for t,c in lines[s]:
                if c + Costs[s] < Costs[t]:
                    Costs[t] = Costs[s]+c
                    
                    if i >= N:
                        Costs[t] = -INF

        if i == N-1: 
            tmp = Costs[Goal]

        

    if tmp != Costs[Goal]:
        return -INF
    else:
        return Costs[Goal]

ans = -BellmanFord(0,N-1)
if ans == INF:
    print(-1)
else:
    print(max(0,ans))