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 math import sin, cos, tan, asin, acos, atan, sqrt, floor, ceil, pi, log10, log, gcd, hypot
from itertools import accumulate, permutations, combinations
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from copy import deepcopy
from decimal import Decimal
import heapq
import sys

mod = 10**9 + 7



sys.setrecursionlimit(10**7)
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class BIT():
    
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def to_sum(self, i):
        
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        
        return self.to_sum(j)-self.to_sum(i-1)


class SegTree():
    
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


class LCA():

    def _bfs(self, node):
        self.visited[node] = True
        for p in tree[node]:
            if self.visited[p] == False:
                self.kprv[0][p] = node
                self.depth[p] = self.depth[node]+1
                self._bfs(p)

    def __init__(self, root, tree):
        self.root = root
        self.n = len(tree)-1
        self.K = (self.n-1).bit_length()
        self.visited = [False for i in range(self.n+1)]
        self.depth = [0 for i in range(self.n+1)]
        self.kprv = [[-1 for i in range(self.n+1)] for j in range(self.K+1)]
        self._bfs(self.root)
        for cnt in range(1, self.K+1):
            for node in range(self.n+1):
                if self.kprv[cnt-1][node] >= 0:
                    self.kprv[cnt][node] = self.kprv[cnt -
                                                     1][self.kprv[cnt-1][node]]
                else:
                    self.kprv[cnt][node] = -1

    def query(self, u, v):
        

        dd = self.depth[v]-self.depth[u]

        if dd < 0:
            u, v = v, u
            dd = -dd

        for i in range(self.K+1):
            if dd & 1:
                v = self.kprv[i][v]
            dd >>= 1
        if u == v:
            return u

        for i in range(self.K-1, -1, -1):
            pu = self.kprv[i][u]
            pv = self.kprv[i][v]
            if pu != pv:
                u = pu
                v = pv
        return self.kprv[0][u]


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


class Graph():
    def __init__(self, N, Type):
        self._V = N  
        self._E = 0  
        self.type = Type
        if Type == "D":
            
            self.G = [[] for i in range(self._V+1)]
        elif Type == "W":
            
            self.G = [[float("inf") for i in range(self._V+1)]
                      for j in range(self._V+1)]
        elif Type == "B" or Type == "K":
            
            self.G = []

    def E(self):
        """ 辺数 """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self._E += 1
        if self.type == "D":
            self.G[_from].append((_to, _cost))

        elif self.type == "W":
            self.G[_from][_to] = _cost

        elif self.type == "B" or self.type == "K":
            self.G.append((_from, _to, _cost))

    def add_both(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する (無向グラフ) """
        self.add(_from, _to, _cost)
        self.add(_to, _from, _cost)


class Dijkstra(Graph):
    def __init__(self, N):
        super().__init__(N, "D")
        self.d = [10**20]*(self._V + 1)
        self.que = []
        heapq.heapify(self.que)

    def shortest_path(self, s):
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[s] = 0
        heapq.heappush(self.que, (0, s))
        while self.que:
            cost, v = heapq.heappop(self.que)
            if self.d[v] < cost:
                continue

            for node, cost in self.G[v]:
                if self.d[node] > self.d[v] + cost:
                    self.d[node] = self.d[v] + cost
                    heapq.heappush(self.que, (self.d[node], node))
        return self.d


class Bellman_Ford(Graph):
    def __init__(self, N):
        super().__init__(N, "B")
        self.d = [10**20]*(self._V+1)

    def shortest_path(self, s):
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[s] = 0
        for _ in range(self._V):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
        return self.d


    def have_negative_circle(self):
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[1] = 0
        for i in range(1, self._V+1):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
            if i == self._V:
                return True
        return False


class Warshall_Floyd(Graph):

    def __init__(self, N):
        super().__init__(N, "W")


    def shortest_path(self):
        
        _N = self._V
        for i in range(_N+1):
            self.G[i][i] = 0
        for k in range(1, _N+1):
            for i in range(1, _N+1):
                for j in range(1, _N+1):
                    self.G[i][j] = min(self.G[i][j], self.G[i][k]+self.G[k][j])
        return self.G


class Kruskal(Graph):
    def __init__(self, N):
        super().__init__(N, "K")
        self.connected_G = UnionFind(self._V)


    def find_lowest_cost(self):
        res = 0
        self.G.sort()
        for p, q, cost in self.G:
            if not self.connected_G.same(p, q):
                self.connected_G.union(p, q)
                res += cost
        return res


def union_lcm(lists):
    if len(lists) == 1:
        return lists[0]
    elif len(lists) > 1:
        num = lists[0]
        for i in range(1, len(lists)):
            num = num*lists[i]//gcd(num, lists[i])
        return num


def union_gcd(lists):
    if len(lists) == 1:
        return lists[0]
    elif len(lists) > 1:
        num = lists[0]
        for i in range(1, len(lists)):
            num = gcd(num, lists[i])
        return num


def is_prime(N):
    for i in range(2, N+1):
        if i**2 > N:
            break
        if N % i == 0:
            return False
    return True


class Primes():
    def __init__(self, N):
        self.N = N
        self.prime = {i for i in range(2, self.N+1)}
        for i in range(2, self.N+1):
            if i in self.prime:
                for j in range(i*2, self.N+1, i):
                    if j in self.prime:
                        self.prime.remove(j)

    def show_primes(self):
        return self.prime

    def is_prime(self, X):
        if X < self.N:
            return X in self.prime
        else:
            return "Unknown"


def main():
    

    N, M, P = map(int, input().split())
    graph = []
    d = deque()

    from_1 = [[] for i in range(N+1)]
    from_N = [[] for i in range(N+1)]

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

    accessible_1 = [False for i in range(N+1)]
    accessible_N = [False for i in range(N+1)]

    def dfs_1(s):
        accessible_1[s] = True
        for node in from_1[s]:
            if accessible_1[node] == False:
                dfs_1(node)

    def dfs_N(s):
        accessible_N[s] = True
        for node in from_N[s]:
            if accessible_N[node] == False:
                dfs_N(node)

    dfs_1(1)
    dfs_N(N)

    isok = [False for i in range(N+1)]
    for i in range(N+1):
        if accessible_1[i] and accessible_N[i]:
            isok[i] = True

    G = Bellman_Ford(N)

    while d:
        p, q, weight = d.popleft()
        if isok[p] and isok[q]:
            G.add(p, q, weight)

    if G.have_negative_circle():
        print(-1)
    else:
        print(max(0, -G.shortest_path(1)[N]))


if __name__ == "__main__":
    main()

Solution (Python):
n,m,p = map(int,input().split())
edges = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edges.append((a-1,b-1,c-p))
d = [-float('inf')]*n
d[0] = 0
for i in range(n):
    for u,v,c in edges:
        if d[u] != -float('inf') and d[u]+c > d[v]:
            d[v] = d[u]+c
            if i ==n-1:
                d[v] = float('inf')

for i in range(n):
    for u,v,c in edges:
        if d[u] != -float('inf') and d[u]+c > d[v]:
            d[v] = d[u]+c
ans = d[-1]
if ans ==float('inf'):
    print(-1)
elif ans <=0:
    print(0)
else:
    print(ans)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N,M,P = LI()

import collections

class BellmanFord():
    def __init__(self,N):  
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  
            self.e[u].append((v,d))
    def BellmanFord_negative_bool2(self,s,t):  
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        if i != self.N - 1:
                            d[v] = d[u] + c
                        else:
                            d[v] = -float('inf')
                            for i in range(self.N):
                                for u in self.e.keys():
                                    for v, c in self.e[u]:
                                        if d[v] > d[u] + c:
                                            d[v] = d[u] + c
                            if d[t] == -float('inf'):
                                return True, d
                            else:
                                return False, d
        return False,d

G = BellmanFord(N)

for i in range(M):
    a,b,c = LI()
    G.add(a,b,P-c,directed=True)

bool,d = G.BellmanFord_negative_bool2(1,N)

if not bool:
    print(max(0,-d[N]))
else:
    print(-1)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N,M,P = LI()

import collections

class BellmanFord():
    def __init__(self,N):  
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):  
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        if i != self.N - 1:
                            d[v] = d[u] + c
                        else:
                            d[v] = -float('inf')
                            for i in range(self.N):
                                for u in self.e.keys():
                                    for v, c in self.e[u]:
                                        if d[v] > d[u] + c:
                                            d[v] = d[u] + c
                            if d[N] == -float('inf'):
                                return True, d
                            else:
                                return False, d
        return False,d

G = BellmanFord(N)

for i in range(M):
    a,b,c = LI()
    G.add(a,b,P-c,directed=True)

a,d = G.BellmanFord_negative_bool(1)

if not a:
    print(max(0,-d[N]))
else:
    print(-1)

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

def main():
  n, m, p = map(int, input().split())
  edge = []
  for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a, b, p-c))
  dist = [float("inf")]*(n+1)
  dist[1] = 0
  for i in range(n):
    for a, b, c in edge:
      if dist[b] > dist[a] + c:
        dist[b] = dist[a] + c
  ans = min(dist[n], 0)
  for i in range(n):
    for a, b, c in edge:
      if dist[b] != -float("inf") and dist[b] > dist[a] + c:
        dist[b] = -float("inf")
  if dist[n] == -float("inf"):
    ans = 1
  print(-ans)
if __name__ == "__main__":
  main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 18
sys.setrecursionlimit(10 ** 5)


def main():
    n, m, p = map(int, readline().split())
    edge = [[] for _ in range(n)]

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

    dist = [INF] * n
    dist[0] = 0

    for _ in range(n - 1):
        for u in range(n):
            for v, w in edge[u]:
                if dist[u] != INF:
                    dist[v] = min(dist[v], dist[u] + w)

    for _ in range(n):
        for u in range(n):
            for v, w in edge[u]:
                if dist[u] != INF and dist[v] > dist[u] + w:
                    dist[v] = -INF

    if dist[n - 1] == -INF:
        print(-1)
    else:
        print(max(-dist[n - 1], 0))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict

    n, m, p = map(int, readline().split())
    edge = defaultdict(list)

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

    dist = [INF] * n
    dist[0] = 0

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

    for _ in range(n):
        for u in range(n):
            for v, w in edge[u]:
                if dist[v] > dist[u] + w:
                    dist[v] = -INF

    if dist[n - 1] == -INF:
        print(-1)
    else:
        print(max(-dist[n - 1], 0))


if __name__ == '__main__':
    main()

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import sys
sys.setrecursionlimit(1000000)

import collections

N, M, P = rl()
E = []
edges = collections.defaultdict(list)
redges = collections.defaultdict(list)
for i in range(M):
	a, b, c = rl()
	E.append((a-1, b-1, P-c))
	edges[a-1].append(b-1)
	redges[b-1].append(a-1)

visited = {}
def dfs(n):
	if n in visited: return
	visited[n] = 1
	for e in edges[n]:
		dfs(e)
rvisited = {}
def rdfs(n):
	if n in rvisited: return
	rvisited[n] = 1
	for e in redges[n]:
		rdfs(e)

dfs(0)
rdfs(N-1)
ok = [False] * N
for n in range(N):
	if n in visited and n in rvisited:
		ok[n] = True
V = list(range(N))

def belmanford(V, E, s=0):
	D = [float('inf')] * len(V)
	D[s] = 0
	P = [None] * len(V)
	update = True
	step = 0
	while update:
		update = False
		for u, v, c in E:
			if not ok[u]: continue
			if not ok[v]: continue
			if D[v] > D[u] + c:
				D[v] = D[u] + c
				P[v] = (u, c)
				update = True
		step += 1
		if step > N:
			return None, None
	return D, P

D, P = belmanford(V, E)
if D == None:
	print(-1)
else:
	print(max(-D[N-1], 0))

Solution (Python):
INF=10**30
def Belman_Ford(s,N,Edge):
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg
                
N,M,P=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    Edge.append((a-1,b-1,-(c-P)))
dist,neg=Belman_Ford(0,N,Edge)

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

Solution (Python):
from collections import deque
import sys


class mEdge():

    def __init__(self, _from, _to, _cost):
        self.From = _from
        self.to = _to
        self.cost = _cost


class bellman_ford():
    def __init__(self, V):
        self.G = []
        self._V = N
        self._E = 0

    def add(self, _from, _to, _cost):
        self.G.append(mEdge(_from, _to, _cost))
        self._E += 1

    def shortest_path(self, s):
        d = [10**20]*(self._V+1)
        d[s] = 0
        for _ in range(self._V):
            flag = False
            for edge in self.G:
                newlen = d[edge.From]+edge.cost
                if newlen < d[edge.to]:
                    flag = True
                    d[edge.to] = newlen
            if not flag:
                break
        return d

    def have_negative_circle(self):
        d = [10**20]*(self._V+1)
        d[1] = 0
        for i in range(1, self._V+1):
            flag = False
            for edge in self.G:
                newlen = d[edge.From]+edge.cost
                if newlen < d[edge.to]:
                    flag = True
                    d[edge.to] = newlen
            if not flag:
                break
            if i == self._V:
                return True
        return False



sys.setrecursionlimit(10**7)
N, M, P = map(int, input().split())
graph = []
d = deque()


from_1 = [[] for i in range(N+1)]
from_N = [[] for i in range(N+1)]

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


accessible_1 = [False for i in range(N+1)]
accessible_N = [False for i in range(N+1)]


def dfs_1(s):
    accessible_1[s] = True
    for node in from_1[s]:
        if accessible_1[node] == False:
            dfs_1(node)


def dfs_N(s):
    accessible_N[s] = True
    for node in from_N[s]:
        if accessible_N[node] == False:
            dfs_N(node)


dfs_1(1)
dfs_N(N)

isok = [False for i in range(N+1)]
for i in range(N+1):
    if accessible_1[i] and accessible_N[i]:
        isok[i] = True
G = bellman_ford(N)

while d:
    p, q, weight = d.popleft()
    if isok[p] and isok[q]:
        G.add(p, q, weight)

if G.have_negative_circle():
    print(-1)
else:

    print(max(0, -G.shortest_path(1)[N]))

Solution (Python):
from collections import deque
import sys


class mEdge():

    def __init__(self, _from, _to, _cost):
        self.From = _from
        self.to = _to
        self.cost = _cost


class bellman_ford():
    def __init__(self, V):
        self.G = []
        self._V = N
        self._E = 0

    def add(self, _from, _to, _cost):
        self.G.append(mEdge(_from, _to, _cost))
        self._E += 1

    def shortest_path(self, s):
        d = [10**20]*(self._V+1)
        d[s] = 0
        for _ in range(self._V):
            flag = False
            for edge in self.G:
                newlen = d[edge.From]+edge.cost
                if newlen < d[edge.to]:
                    flag = True
                    d[edge.to] = newlen
            if not flag:
                break
        return d

    def have_negative_circle(self):
        d = [10**20]*(self._V+1)
        d[1] = 0
        for i in range(1, self._V+1):
            flag = False
            for edge in self.G:
                newlen = d[edge.From]+edge.cost
                if newlen < d[edge.to]:
                    flag = True
                    d[edge.to] = newlen
            if not flag:
                break
            if i == self._V:
                return True
        return False



sys.setrecursionlimit(10**7)
N, M, P = map(int, input().split())
graph = []
d = deque()


from_1 = [[] for i in range(N+1)]
from_N = [[] for i in range(N+1)]

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


accessible_1 = [False for i in range(N+1)]
accessible_N = [False for i in range(N+1)]


def dfs_1(s):
    accessible_1[s] = True
    for node in from_1[s]:
        if accessible_1[node] == False:
            dfs_1(node)


def dfs_N(s):
    accessible_N[s] = True
    for node in from_N[s]:
        if accessible_N[node] == False:
            dfs_N(node)


dfs_1(1)
dfs_N(N)

isok = [False for i in range(N+1)]
for i in range(N+1):
    if accessible_1[i] and accessible_N[i]:
        isok[i] = True
G = bellman_ford(N)

while d:
    p, q, weight = d.popleft()
    if isok[p] and isok[q]:
        G.add(p, q, weight)

if G.have_negative_circle():
    print(-1)
else:

    print(max(0, -G.shortest_path(1)[N]))

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, M, P = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

to = [[] for _ in range(N + 1)]
ot = [[] for _ in range(N + 1)]
edges = [[] for _ in range(N + 1)]

for a, b, c in X:
    edges[a].append((b, c - P))
    to[a].append(b)
    ot[b].append(a)

ok_1 = [False] * (N + 1)
ok_n = [False] * (N + 1)
ok_1[1] = True
ok_n[N] = True

q = deque()
q.append(1)
while q:
    u = q.popleft()
    for v in to[u]:
        if not ok_1[v]:
            ok_1[v] = True
            q.append(v)
            
q = deque()
q.append(N)
while q:
    u = q.popleft()
    for v in ot[u]:
        if not ok_n[v]:
            ok_n[v] = True
            q.append(v)

INF = 10 ** 9 + 7
d = [INF] * (N + 1)
d[1] = 0
updated = True
cnt = 0
while updated and cnt <= N:
    updated = False
    cnt += 1
    for u in range(1, N + 1):
        if not ok_1[u] or not ok_n[u]:
            continue
            
        for v, c in edges[u]:
            if not ok_1[v] or not ok_n[v]:
                continue
                
            if d[v] > d[u] - c:
                d[v] = d[u] - c
                updated = True

if cnt > N:
    print(-1)
else:
    print(max(0, -d[-1]))

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, M, P = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

to = [[] for _ in range(N + 1)]
ot = [[] for _ in range(N + 1)]
edges = [[] for _ in range(N + 1)]

for a, b, c in X:
    edges[a].append((b, c - P))
    to[a].append(b)
    ot[b].append(a)

ok_1 = [False] * (N + 1)
ok_n = [False] * (N + 1)

def dfs_1(u):
    if ok_1[u]:
        return
    
    ok_1[u] = True
    for v in to[u]:
        dfs_1(v)
        
def dfs_n(u):
    if ok_n[u]:
        return
    
    ok_n[u] = True
    for v in ot[u]:
        dfs_n(v)

dfs_1(1)
dfs_n(N)

INF = 10 ** 9 + 7
d = [INF] * (N + 1)
d[1] = 0
updated = True
cnt = 0
while updated and cnt <= N:
    updated = False
    cnt += 1
    for u in range(1, N + 1):
        if not ok_1[u] or not ok_n[u]:
            continue
            
        for v, c in edges[u]:
            if not ok_1[v] or not ok_n[v]:
                continue
                
            if d[v] > d[u] - c:
                d[v] = d[u] - c
                updated = True

if cnt > N:
    print(-1)
else:
    print(max(0, -d[-1]))

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

def main():
  n, m, p = map(int, input().split())
  edge = []
  for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a, b, c-p))
  dist = [-float("inf")]*(n+1)
  dist[1] = 0
  for i in range(n):
    for a, b, c in edge:
      if dist[b] < dist[a] + c:
        dist[b] = dist[a] + c
  ans = max(dist[n], 0)
  for i in range(n):
    for a, b, c in edge:
      if dist[b] != float("inf") and dist[b] < dist[a] + c:
        dist[b] = float("inf")
  if dist[n] == float("inf"):
    ans = -1
  print(ans)
if __name__ == "__main__":
  main()

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

n, m, p = map(int, input().split())
edge = []
for _ in range(m):
  a, b, c = map(int, input().split())
  edge.append((a, b, c-p))
dist = [-float("inf")]*(n+1)
dist[1] = 0
for i in range(n):
  for a, b, c in edge:
    if dist[b] < dist[a] + c:
      dist[b] = dist[a] + c
ans = max(dist[n], 0)
for i in range(n):
  for a, b, c in edge:
    if dist[b] != float("inf") and dist[b] < dist[a] + c:
      dist[b] = float("inf")
if dist[n] == float("inf"):
  ans = -1
print(ans)