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
import sys
input = sys.stdin.readline


def main():
    N, M, P = map(int, input().split())
    edge = []
    g = [[] for _ in range(N)]
    rg = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge.append((A,B,C))
        g[A].append(B)
        rg[B].append(A)

    
    
    
    visited1 = set() 
    visited2 = set()
    visited1.add(0)
    visited2.add(N-1)
    Q = deque()
    Q.append(0)
    while Q:
        v = Q.popleft()
        for dest in g[v]:
            if dest in visited1:
                continue
            visited1.add(dest)
            Q.append(dest)
    
    Q.append(N-1)
    while Q:
        v = Q.popleft()
        for dest in rg[v]:
            if dest in visited2:
                continue
            visited2.add(dest)
            Q.append(dest)
    
    OK = visited1 & visited2
    
    flag = True
    d = [float('inf')] * N
    d[0] = 0
    
    for _ in range(N):
        flag = False
        for a, b, c in edge:
            if not a in OK:
                continue
            if not b in OK:
                continue
            newD = d[a] + c
            if newD < d[b]:
                d[b] = newD
                flag = True
        if not flag:
            print(max(0,-d[N-1]))
            exit()
    else:
        print(-1)
        exit()


if __name__ == "__main__":
    main()

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


def main():
    N, M, P = map(int, input().split())
    edge = [[] for _ in range(N)]
    redge = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge[A].append((B,C))
        redge[B].append(A)

    
    
    
    visited1, visited2 = {0}, {N-1}
    
    stack = [0]
    while stack:
        v = stack.pop()
        for dest, _ in edge[v]:
            if dest in visited1:
                continue
            visited1.add(dest)
            stack.append(dest)
    
    stack = [N-1]
    while stack:
        v = stack.pop()
        for dest in redge[v]:
            if dest in visited2:
                continue
            visited2.add(dest)
            stack.append(dest)
    
    OK = visited1 & visited2
    
    new_edge = [[] for _ in range(N)]
    for s in range(N):
        for t, c in edge[s]:
            if t in OK:
                new_edge[s].append((t,c))

    flag = True
    d = [float('inf')] * N
    d[0] = 0
    
    for _ in range(N):
        flag = False
        for v, e in enumerate(new_edge):
            for t, c in e:
                if d[v] != float('inf') and d[v] + c < d[t]:
                    d[t] = d[v] + c
                    flag = True
        if not flag:
            print(max(0,-d[N-1]))
            exit()
    else:
        print(-1)
        exit()


if __name__ == "__main__":
    main()

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


def main():
    N, M, P = map(int, input().split())
    A, B, C = [0] * M, [0] * M, [0] * M
    v = [set() for _ in range(N)]
    u = [set() for _ in range(N)]
    for i in range(M):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a - 1, b - 1, P - c
        u[a - 1].add(b - 1)
        v[b - 1].add(a - 1)
    vv = set()
    cur = set([N - 1])
    while cur:
        vv |= cur
        cur = set().union(*(v[c] for c in cur)) - vv
    uu = set()
    cur = set([0])
    while cur:
        uu |= cur
        cur = set().union(*(u[c] for c in cur)) - uu
    reachable = vv & uu
    l = {}
    for a, b, c in zip(A, B, C):
        if a in reachable and b in reachable:
            l[(a, b)] = min(c, l.get((a, b), 10 **9))
    AA, BB, CC = [], [], []
    for (a, b), c in l.items():
        AA.append(a)
        BB.append(b)
        CC.append(c)
    mx = csr_matrix((CC, (AA, BB)), shape=(N, N))
    try:
        dm = bellman_ford(mx, indices=[0])
    except NegativeCycleError:
        return -1
    return max(0, -int(dm[0][N - 1]))


print(main())

Solution (Python):
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) 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 II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M,P=LI()
EDGES = []
E1 = [[] for i in range(N+1)]
E2 = [[] for i in range(N+1)]

for i in range(M):
    F,T,C=LI()
    EDGES.append((F,T,P-C))
    E1[F].append(T)
    E2[T].append(F)

def bellman_ford(edges):
    
    DIST=[10**18]*(N+1)
    DIST[1] = 0
    for i in range(N):
        for j in range(len(edges)):
            fr, to, cost = edges[j]
            if (DIST[to] > DIST[fr] + cost):
                if (i == N-1):
                    print(-1)
                    exit()
                else:
                    DIST[to] = DIST[fr] + cost
    
    print(max(-DIST[-1], 0))

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

use = dfs(E1,1) & dfs(E2, N)

bellman_ford([(a,b,c) for a,b,c in EDGES if (a in use and b in use)])

Solution (Python):
N,M,P = map(int,input().split())
E = []
for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c=-c+P
  E.append([a,b,c])
  
def BellmanFord(s,g):
  
  inf=float("inf")
  dist=[inf for i in range(N)]
  dist[s]=0
  rout=[]
  
  
  for i in range(N):
    for edge in E:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==N-1: dist[edge[1]]=-inf
  for i in range(N):
    for edge in E:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
  if dist[g] == -inf:return -1
  return max(0,-dist[g])
print(BellmanFord(0,N-1))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


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

    nodes = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        nodes.append((a - 1, b - 1, -(c - p)))
    
    d = [float("inf") for _ in range(n)]
    pre = [-1 for _ in range(n)]
    d[0] = 0
    for _ in range(n):
        for nod in nodes:
            if d[nod[1]] > d[nod[0]] + nod[2]:
                d[nod[1]] = d[nod[0]] + nod[2]
                pre[nod[1]] = nod[0]

    for i, nod in enumerate(nodes):
        if d[nod[1]] > d[nod[0]] + nod[2]:
            nodes[i] = (nod[0], nod[1], -float('inf'))
    
    d = [float("inf") for _ in range(n)]
    pre = [-1 for _ in range(n)]
    d[0] = 0
    for _ in range(n):
        for nod in nodes:
            if d[nod[1]] > d[nod[0]] + nod[2]:
                d[nod[1]] = d[nod[0]] + nod[2]
                pre[nod[1]] = nod[0]

    path = set()
    fr = n - 1
    while pre[fr] != -1:
        if fr in path:
            break
        path.add(pre[fr])
        fr = pre[fr]

    for nod in nodes:
        if d[nod[1]] > d[nod[0]] + nod[2]:
            if nod[0] in path:
                print(-1)
                return

    if d[n - 1] == -float('inf'):
        print(-1)
        return 

    if d[n - 1] > 0:
        print(0)
    else:
        print(-d[n - 1])
    

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10**10
 
class ExtendedBellmanFord:
    def __init__(self, edge):
        self.f_edge = edge
        self.b_edge = [[] for _ in range(len(edge))]
        for src, es in enumerate(edge):
            for dst, cost in es:
                self.b_edge[dst].append((src, -cost))

    def bellman_ford(self, mask, start):
        dist = [INF] * n
        dist[start] = 0
        for _ in range(n):
            update = False
            for i, es in enumerate(self.f_edge):
                if not mask[i]:
                    continue
                for to, cost in es:
                    if not mask[to]:
                        continue
                    if dist[i] != INF and dist[i] + cost < dist[to]:
                        dist[to] = dist[i] + cost
                        update = True
            if not update:
                return dist
        else:
            
            return -INF

    def calc(self, start, end):
        visited = [False] * n
        visited[start] = True
        st = [start]
        while st:
            node = st.pop()
            for to, _ in self.f_edge[node]:
                if not visited[to]:
                    visited[to] = True
                    st.append(to)
        rvisited = [False] * n
        rvisited[end] = True
        st = [end]
        while st:
            node = st.pop()
            for to, _ in self.b_edge[node]:
                if not rvisited[to]:
                    rvisited[to] = True
                    st.append(to)
        mask = [forward and backward for forward, backward in zip(visited, rvisited)]
        dist = self.bellman_ford(mask, start)
        if dist == -INF:
            return -INF
        else:
            return dist[end]

if __name__ == "__main__":
    n, m, p = [int(item) for item in input().split()]
    edge = [[] for _ in range(n)]
    for i in range(m):
        a, b, c = [int(item) for item in input().split()]
        a -= 1; b -= 1; c -= p
        c *= -1
        edge[a].append((b, c))
    
    EBF = ExtendedBellmanFord(edge)
    ret = EBF.calc(0, n-1)
    if ret == -INF:
        print(-1)
    else:
        print(max(0, -ret))

Solution (Python):
import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

class BellmanFord():
	def __init__(self, adj, start, size):
		self.adj = adj
		self.start = start
		self.size = size
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if s_reachable[x] and s_reachable[y] and g_reachable[x] and g_reachable[y]:
						if self.dist[y] > self.dist[x] + w:
							self.dist[y] = self.dist[x] + w
		for x in range(self.size):
			for y, w in self.adj[x]:
				if s_reachable[x] and s_reachable[y] and g_reachable[x] and g_reachable[y]:
					if self.dist[y] > self.dist[x] + w:
						return False

		return True

	def GetDistance(self, goal):
		return self.dist[goal]

n, m, p = map(int, input().split())
adj = [[] for _ in range(n)]
adj_rev = [[] for _ in range(n)]

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

s_reachable = [False for _ in range(n)]
s_reachable[0] = True
g_reachable = [False for _ in range(n)]
g_reachable[n-1] = True

def dfs_s(x):
	for v, w in adj[x]:
		if not s_reachable[v]:
			s_reachable[v] = True
			dfs_s(v)
	return

def dfs_g(x):
	for v in adj_rev[x]:
		if not g_reachable[v]:
			g_reachable[v] = True
			dfs_g(v)
	return

dfs_s(0)
dfs_g(n-1)

bf = BellmanFord(adj, 0, n)
if not bf.solve():
	print(-1)
else:
	print(max(-bf.GetDistance(n-1), 0))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    
    res = [INF] * N
    res[src] = 0
    
    for _ in range(N-1):
        for u, v, cost in edges:
            
            if res[u] == INF:
                continue
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    tmp = res[:]
    
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[u] == INF:
                continue
            if res[v] > res[u] + cost:
                
                res[v] = -INF
    for i in range(N):
        if tmp[i] != res[i]:
            res[i] = -INF
    return res

N, M, P = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, P-c))

res = bellman_ford(N, edges, 0)

if res[N-1] != -INF:
    print(max(-res[N-1], 0))
else:
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m,p=map(int,input().split())
g=[[] for _ in range(n)]
g2=[[] for _ in range(n)]
g3=[[] for _ in range(n)]
for _ in range(m):
    a,b,l=map(int,input().split())
    g[a-1].append([b-1,p-l])
    g2[a-1].append(b-1)
    g3[b-1].append(a-1)

f1=[False for _ in range(n)]
def dfs1(s):
    global f1
    global g2
    f1[s] = True
    for sg in g2[s]:
        if not f1[sg]:
            dfs1(sg)
f2=[False for _ in range(n)]
def dfs2(s):
    global f2
    global g3
    f2[s] = True
    for sg in g3[s]:
        if not f2[sg]:
            dfs2(sg)

dfs1(0)
dfs2(n-1)
f3 = []
for i in range(n):
    f3.append(f1[i] and f2[i])

def bellman_ford(g,n):
    INF = 10**10
    res = [INF for _ in range(n)]
    res[0] = 0
    for _ in range(n-1):
        for i in range(n):
            if res[i] != INF:
                for sa,sb in g[i]:
                    res[sa] = min(res[sa],res[i]+sb)
    ret = res[-1]
    for i in range(n):
        if res[i] != INF:
            for sa,sb in g[i]:
                if res[sa]>res[i]+sb:
                    if f3[sa]:
                        return False
    return ret

res = bellman_ford(g,n)
if type(res) == bool:
    print(-1)
elif res > 0:
    print(0)
else:
    print(res * -1)

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

n,m,p=map(int,input().split())
g=[[] for _ in range(n)]
g2=[[] for _ in range(n)]
g3=[[] for _ in range(n)]
for _ in range(m):
    a,b,l=map(int,input().split())
    g[a-1].append([b-1,p-l])
    g2[a-1].append(b-1)
    g3[b-1].append(a-1)

f1=[False for _ in range(n)]
def dfs1(s):
    global f1
    global g2
    f1[s] = True
    for sg in g2[s]:
        if not f1[sg]:
            dfs1(sg)
f2=[False for _ in range(n)]
def dfs2(s):
    global f2
    global g3
    f2[s] = True
    for sg in g3[s]:
        if not f2[sg]:
            dfs2(sg)

dfs1(0)
dfs2(n-1)
f3 = []
for i in range(n):
    f3.append(f1[i] and f2[i])

def bellman_ford(g,n):
    INF = 10**10
    res = [INF for _ in range(n)]
    res[0] = 0
    for _ in range(n-1):
        for i in range(n):
            if res[i] != INF:
                for sa,sb in g[i]:
                    res[sa] = min(res[sa],res[i]+sb)
    ret = res[-1]
    for i in range(n):
        if res[i] != INF:
            for sa,sb in g[i]:
                if res[sa]>res[i]+sb:
                    if f3[sa]:
                        return False
    return ret

res = bellman_ford(g,n)
if type(res) == bool:
    print(-1)
elif res > 0:
    print(0)
else:
    print(res * -1)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m,p=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        u,v,c=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,p-c))
        R[v].append((u,p-c))

    
    state=[0]*n
    state[0]+=1
    state[-1]+=2

    Q=[0]
    while(Q):
        v=Q.pop()
        for nv,w in E[v]:
            if(state[nv]&1): continue
            state[nv]+=1
            Q.append(nv)

    Q=[n-1]
    while(Q):
        v=Q.pop()
        for nv,w in R[v]:
            if(state[nv]&2): continue
            state[nv]+=2
            Q.append(nv)

    
    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        update=False
        for v in range(n):
            if(state[v]!=3): continue
            for nv,w in E[v]:
                if(state[nv]!=3): continue
                if(dist[nv]>dist[v]+w):
                    dist[nv]=dist[v]+w
                    update=True
        if(not update):
            break
        if(update and k==n-1):
            print(-1)
            return

    print(max(0,-dist[-1]) if(dist[-1]!=INF) else -1)
resolve()

Solution (Python):
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]

def bellman_ford(v, s, e):
    INF = 10**18
    
    d = [INF] * v
    
    d[s] = 0
    
    for _ in range(v):
        f = False
        for a, b, c in e:
            
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        
        if not f:
            break
    else:
        
        print(-1)
        exit()
    print(max(-d[-1],0))

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


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
use=dfs(l,0)&dfs(ll,n-1)
e=[(a,b,c) for a,b,c in e if (a in use and b in use)]


bellman_ford(n, 0, e)

Solution (Python):
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]

def bellman_ford(v, s, e):
    INF = 10**18
    
    d = [INF] * v
    
    d[s] = 0
    
    for _ in range(v):
        f = False
        for a, b, c in e:
            
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        
        if not f:
            break
    else:
        
        print(-1)
        exit()
    print(max(-d[-1],0))

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


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
use=dfs(l,0)&dfs(ll,n-1)
e=[(a,b,c) for a,b,c in e if (a in use and b in use)]


bellman_ford(n, 0, e)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase


input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    
    
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    
    for i in range(num_v):

        if i==num_v-1:
            check=dist[n-1]
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:
                    
                    neg_flg=True
                neg[v] = True
    
    return neg_flg,dist
 

show_flg=False
show_flg=True


n,m,p=MI()
g=[[] for i in range(n)]
rg=[[] for i in range(n)]
for i in range(m):
    a,b,c=LI_()
    c+=1
    
    g[a].append((b,p-c))
    rg[b].append(a)
    
q=[n-1]
v=[0 for i in range(n)]
v[n-1]=1
while q:
    c=q.pop()
    for nb in rg[c]:
        if v[nb]==0:
            v[nb]=1
            q.append(nb)

for i in range(n):
    if v[i]==0:
        g[i]=[]

fl,d=BellmanFord(g,n,0)
ans=d[n-1]

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

Solution (Python):
def BellmanFord(edges,num_v,source):
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
        if i==num_v-1: dist[edge[1]-1] = -inf
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
  r = dist[-1]
  if r > 0: r = 0
  if r < 0: r=-r
  if r == inf: r=-1
  return r

import sys
input = sys.stdin.readline
N, M, P = map(int, input().split())
edges = []
for i in range(M):
    A, B, C = map(int, input().split())
    edges.append([A, B, P-C])
print(BellmanFord(edges, N, 1))

Solution (Python):
from collections import deque

N,M,P = map(int, input().split())
E = [[] for _ in range(N)]
Ei = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int, input().split())
    E[a-1].append((b-1, -c+P))
    Ei[b-1].append(a-1)
    
q = deque()
q.append(0)
used = [0]*N
used[0] = 1
while q:
    t = q.pop()
    for e in E[t]:
        if used[e[0]] == 1:
            continue
        used[e[0]] = 1
        q.append(e[0])
        
q.append(N-1)
used2 = [0]*N
used2[N-1] = 1
while q:
    t = q.pop()
    for e in Ei[t]:
        if used2[e] == 1:
            continue
        used2[e] = 1
        q.append(e)
        
L = [0]*N
for i in range(N):
    if used[i] == 1 and used2[i] == 1:
        L[i] = 1
    
def BellmanFord(E, N, source):
    inf = 10**10
    d = [inf for _ in range(N)]
    d[source] = 0
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j]+edge[1]:
                    d[edge[0]] = d[j]+edge[1]
                    if i >= N-1 and L[edge[0]] == 1:
                        return -1
    return d

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

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

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,P-C])

def Bellman_Ford(edges, start, N):
    inf = float("inf")
    
    dist = [inf for i in range(N)]
    dist[start] = 0

    for i in range(N+N):
        for a,b,c in edges:
            if a != inf and dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                
                if i >= N:
                    dist[b] = -inf
        
        if i == N-1:
            first_time = dist[-1]
    
    return first_time, dist[-1]

first,second = Bellman_Ford(edge, 0, N)
if first != second:
    answer = -1
else:
    answer = max(0,-second)

print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m,p=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        u,v,c=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,p-c))
        R[v].append((u,p-c))

    
    state=[0]*n
    state[0]+=1
    state[n-1]+=2

    
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv,w in E[v]:
            if(state[nv]&1): continue
            state[nv]+=1
            Q.append(nv)

    
    Q=[n-1]
    while(Q):
        v=Q.pop()
        for nv,w in R[v]:
            if(state[nv]&2): continue
            state[nv]+=2
            Q.append(nv)

    
    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        flag=0
        for v in range(n):
            for nv,w in E[v]:
                if(state[v]&state[nv]!=3): continue
                if(dist[nv]>dist[v]+w):
                    dist[nv]=dist[v]+w
                    flag=1
        if(flag and k==n-1):
            print(-1)
            return

    print(max(-dist[-1],0))
resolve()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

def bellman_ford(start, goal, N, edges,
                 get_route=False,
                 negative_loop=None,
                 start_distance=0,
                 plus_func=lambda D,d: D+d):
    '''
    goal: int or list or set
    edges: list or dict
        edges[x] = {(y0, distance0), ...}
    '''
    distance = [None]*N
    predecessor = [None]*N
    if isinstance(goal, int):
        goal = [goal]
    elif isinstance(goal, set):
        goal = list(goal)
    M = len(goal)
    goalable = [[False]*N for _ in range(M)]
    for m in range(M):
        goalable[m][goal[m]] = True
    distance[start] = start_distance
    for _ in range(N-1):
        for i in range(N):
            if distance[i] is None:
                continue
            for j, d in edges[i]:
                for m in range(M):
                    if goalable[m][j]:
                        goalable[m][i] = True
                p = plus_func(distance[i], d)
                if distance[j] is None or distance[j] > p:
                    distance[j] = p
                    predecessor[j] = i

    goal_valid = [True]*M
    for i in range(N):
        if distance[i] is None:
            continue
        for j, d in edges[i]:
            if distance[j] is not None and plus_func(distance[i], d) < distance[j]:
                
                for m in range(M):
                    if goal_valid[m] and goalable[m][i]:
                        distance[goal[m]] = negative_loop
                        goal_valid[m] = False
    if get_route:
        return distance, predecessor
    else:
        return distance

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

distance = bellman_ford(0, N-1, N, uv)
minus_ans = distance[-1]
if minus_ans is None:
    print(-1)
elif minus_ans > 0:
    print(0)
else:
    print(-minus_ans)