AtCoder Beginner Contest 137 - Coins Respawn

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-----
3 3 10
1 2 20
2 3 30
1 3 45

-----Sample Output-----
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.

Difficulty: MEDIUM

Starter code:

Solutions:
(n, m, p) = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for _ in range(m)]
for i in e:
	i[0] -= 1
	i[1] -= 1
	i[2] -= p
d = [-10 ** 18] * n
ok1 = [False] * n
ok2 = [False] * n
d[0] = 0
ok1[0] = True
ok2[-1] = True
for _ in range(n):
	for (a, b, c) in e:
		if ok1[a]:
			d[b] = max(d[b], d[a] + c)
			ok1[b] = True
		if ok2[b]:
			ok2[a] = True
aa = d[:]
for _ in range(1):
	for (a, b, c) in e:
		if ok1[a]:
			d[b] = max(d[b], d[a] + c)
			ok1[b] = True
		if ok2[b]:
			ok2[a] = True
bb = d[:]
ok = False
for i in range(n):
	if ok1[i] and ok2[i]:
		if aa[i] != bb[i]:
			ok = True
if ok:
	print('-1')
else:
	print(max(aa[-1], 0))


def BF(v, start, edges):
	INF = 10 ** 18
	nega = False
	d = [INF] * v
	d[start] = 0
	for _ in range(v):
		f = False
		for (a, b, c) in edges:
			cost = d[a] + c
			if cost < d[b]:
				d[b] = cost
				f = True
		if not f:
			break
	else:
		nega = True
	return (d, nega)
from collections import deque

def BFS(N, graph, start):
	d = [-1 for i in range(N)]
	Q = deque([])
	Q.append(start)
	d[start] = 0
	while Q:
		v = Q.popleft()
		for u in graph[v]:
			if d[u] == -1:
				d[u] = d[v] + 1
				Q.append(u)
	return d
(N, M, P) = (int(i) for i in input().split())
graph = [[] for i in range(N)]
graphr = [[] for i in range(N)]
edges = []
for i in range(M):
	(A, B, C) = (int(i) for i in input().split())
	graph[A - 1].append(B - 1)
	graphr[B - 1].append(A - 1)
	edges.append((A - 1, B - 1, P - C))
d_start = BFS(N, graph, 0)
d_end = BFS(N, graphr, N - 1)
nodes_start = [i for i in range(N) if d_start[i] >= 0]
nodes_end = [i for i in range(N) if d_end[i] >= 0]
new_edges = []
for (A, B, C) in edges:
	if A in nodes_start and B in nodes_start and (A in nodes_end) and (B in nodes_end):
		new_edges.append((A, B, C))
(d, Nega) = BF(N, 0, new_edges)
if Nega == True:
	print(-1)
else:
	print(max(-d[N - 1], 0))


(n, m, p) = map(int, input().split())
edge = []
inv_link = [[] for _ in range(n)]
link = [[] for _ in range(n)]
for i in range(m):
	(a, b, cost) = list(map(int, input().split()))
	edge.append([a - 1, b - 1, p - cost])
	link[a - 1].append(b - 1)
	inv_link[b - 1].append(a - 1)

def bell(edges, start, num_v):
	cost = [float('inf')] * num_v
	cost[start] = 0
	for _ in range(num_v):
		updated = False
		for (a, b, c) in edges:
			if cost[b] > cost[a] + c:
				cost[b] = cost[a] + c
				updated = True
		if not updated:
			break
	else:
		return (False, cost)
	return (True, cost)
from collections import deque
Q = deque()
Q.append([n - 1, 0])
visited = [-1] * n
visited[n - 1] = 0
while Q:
	(now, cnt) = Q.popleft()
	for nxt in inv_link[now]:
		if visited[nxt] != -1:
			continue
		visited[nxt] = cnt + 1
		Q.append([nxt, cnt + 1])
new_edge = []
for (a, b, c) in edge:
	if visited[a] == -1 or visited[b] == -1:
		continue
	new_edge.append([a, b, c])
(ret, cost) = bell(new_edge, 0, n)
if ret:
	print(max(0, -cost[-1]))
else:
	print(-1)


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

def bellmanFord(G, start_vertex):
	distance = [-float('inf') for i in range(n + 1)]
	distance[start_vertex] = 0
	for i in range(2 * n):
		for (node, neighbor, cost) in G:
			if distance[neighbor] < distance[node] + cost:
				if i < n:
					distance[neighbor] = distance[node] + cost
				else:
					distance[neighbor] = float('inf')
		if i == n - 1:
			prev_ans = distance[n]
	if prev_ans != distance[n]:
		return -1
	else:
		return distance[n]
distance = bellmanFord(G, 1)
if distance == -1:
	ans = -1
else:
	ans = max(0, distance)
print(ans)


import sys
sys.setrecursionlimit(10000)
(n, m, p) = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]
al = [[] for _ in range(n)]
for i in range(m):
	abc[i][0] -= 1
	abc[i][1] -= 1
	abc[i][2] = -(abc[i][2] - p)
for (a, b, c) in abc:
	al[a].append(b)
d = [1000000000.0] * n
d[0] = 0
for _ in range(n - 1):
	for (u, v, c) in abc:
		if d[v] > d[u] + c:
			d[v] = d[u] + c
res = -d[-1]
for _ in range(n - 1):
	for (u, v, c) in abc:
		if d[v] > d[u] + c:
			d[v] = d[u] + c
if res != -d[-1]:
	print(-1)
else:
	print(max(res, 0))


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
(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])

def bellnabFord(edges, src, N):
	inf = float('inf')
	dist = [inf for i in range(N)]
	dist[src] = 0
	for i in range(2 * N):
		for (s, d, c) in edges:
			if dist[d] > dist[s] + c:
				dist[d] = dist[s] + c
				if i >= N:
					dist[d] = -float('inf')
			if i == N - 1:
				prev = dist[-1]
	return (prev, dist[-1])
(prev, dist) = bellnabFord(edges, 0, N)
if prev != dist:
	ans = -1
else:
	ans = max(0, -dist)
print(ans)


def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def BellmanFord(V: int, es: list, source=0):
	INF = float('inf')
	D = [INF] * V
	D[source] = 0
	for _ in range(V):
		upd = False
		for (f, t, c) in es:
			tmp = D[f] + c
			if D[t] > tmp:
				D[t] = tmp
				upd = True
		if not upd:
			return D[-1]
	else:
		return None

def main():
	(N, M, P, *L) = map(int, open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	for (a, b) in zip(L[::3], L[1::3]):
		fwd[a - 1].append(b - 1)
		bwd[b - 1].append(a - 1)
	judge = reachable(fwd, 0) & reachable(bwd, N - 1)
	G = [(a - 1, b - 1, P - c) for (a, b, c) in zip(*[iter(L)] * 3) if a - 1 in judge and b - 1 in judge]
	ans = BellmanFord(N, G)
	if ans == None:
		print(-1)
	else:
		print(max(0, -ans))
main()


from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
import sys
input = sys.stdin.readline

def main():
	(n, m, p) = list(map(int, input().split()))
	edges = []
	routes = [[] for _ in range(n)]
	rev_routes = [[] for _ in range(n)]

	def get_reachable_nodes(start, routes):
		seen = {start}
		todo = []
		for to in routes[start]:
			todo.append(to)
			seen.add(to)
		while todo:
			node = todo.pop()
			for to in routes[node]:
				if to in seen:
					continue
				todo.append(to)
				seen.add(to)
		return seen
	for _ in range(m):
		(node1, node2, value) = list(map(int, input().split()))
		(node1, node2, value) = (node1 - 1, node2 - 1, value - p)
		edges.append([node1, node2, value])
		routes[node1].append(node2)
		rev_routes[node2].append(node1)
	from_start = get_reachable_nodes(0, routes)
	if n - 1 not in from_start:
		print(-1)
		return
	to_goal = get_reachable_nodes(n - 1, rev_routes)
	from_start_to_goal = from_start & to_goal
	temp_dict = dict()
	for (row, col, value) in edges:
		if {row, col} <= from_start_to_goal:
			if not (row, col) in temp_dict:
				temp_dict[row, col] = -value
			else:
				temp_dict[row, col] = min(-value, temp_dict[row, col])
	values = []
	rows = []
	cols = []
	for ((row, col), minus_value) in list(temp_dict.items()):
		values.append(minus_value)
		rows.append(row)
		cols.append(col)
	graph = coo_matrix((values, (rows, cols)), shape=(n, n))
	try:
		bf = bellman_ford(graph, indices=[0])
		print(max(0, -int(bf[0][n - 1])))
	except NegativeCycleError:
		print(-1)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
(N, M, P) = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	(a, b, c) = (a - 1, b - 1, c - P)
	G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
	for e in range(N):
		for (w, c) in G[e]:
			if dist[e] != INF and dist[w] > dist[e] + c:
				dist[w] = dist[e] + c
ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
	for e in range(N):
		for (w, c) in G[e]:
			if dist[e] != INF and dist[w] > dist[e] + c:
				dist[w] = dist[e] + c
				is_negative[w] = True
			if is_negative[e]:
				is_negative[w] = True
if is_negative[N - 1]:
	print(-1)
else:
	print(max(ans, 0))


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

def BellmanFord(edges, num_v, s):
	inf = float('inf')
	dist = [inf] * num_v
	dist[s] = 0
	for i in range(num_v - 1):
		for edge in edges:
			if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2] + p:
				dist[edge[1]] = dist[edge[0]] + edge[2] + p
	cnt1 = -dist[n - 1]
	neg = [False] * num_v
	for i in range(num_v):
		for edge in edges:
			if dist[edge[1]] > dist[edge[0]] + edge[2] + p:
				dist[edge[1]] = dist[edge[0]] + edge[2] + p
				neg[edge[1]] = True
			if neg[edge[0]]:
				neg[edge[1]] = True
	if neg[n - 1]:
		ans = -1
	else:
		ans = max(cnt1, 0)
	return ans
edges = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c *= -1
	edges.append((a, b, c))
print(BellmanFord(edges, n, 0))


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, M, P) = lr()
graph = [lr() for _ in range(M)]

def bellmanford(start, N):
	INF = 10 ** 12
	dist = [-INF] * (N + 1)
	dist[start] = 0
	for i in range(N + N + 5):
		for (pre, ne, weight) in graph:
			if dist[pre] != -INF and dist[pre] + weight - P > dist[ne]:
				dist[ne] = dist[pre] + weight - P
				if i > N - 1:
					dist[ne] = INF
	if dist[N] == INF:
		return -1
	else:
		return max(0, dist[N])
answer = bellmanford(1, N)
print(answer)


import sys
input = sys.stdin.readline

def BellmanFord(Edges, num_v, source):
	inf = float('inf')
	dist = [inf for _ in range(num_v)]
	dist[source] = 0
	for i in range(num_v):
		for edge in Edges:
			if edge[0] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
				if i == num_v - 1:
					before_dist = dist[num_v - 1]
					for i in range(num_v):
						for edge in Edges:
							if edge[0] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
								dist[edge[1]] = dist[edge[0]] + edge[2]
					if before_dist != dist[num_v - 1]:
						return -1
	return dist
(n, m, p) = map(int, input().split())
Edges = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	Edges.append((a, b, -(c - p)))
d = BellmanFord(Edges, n, 0)
print(-1 if d == -1 else max(0, -d[-1]))


import sys
sys.setrecursionlimit(1000000000)
ii = lambda : int(input())
miis = lambda : map(int, input().split())
lmiis = lambda : list(miis())

def reachable_nodeset(start, inc):
	reachable = set()
	reachable.add(start)
	nodes = [start]
	while nodes:
		n = nodes.pop()
		for i in inc[n]:
			if i not in reachable:
				nodes.append(i)
				reachable.add(i)
	return reachable

def bellmanford(num, start, goal, edges):
	cost = [float('inf')] * num
	cost[start] = 0
	for _ in range(num):
		updated = False
		for (a, b, c) in edges:
			if cost[b] > cost[a] + c:
				cost[b] = cost[a] + c
				updated = True
		if not updated:
			break
	else:
		return -1
	return max(0, -cost[goal])

def solve():
	(N, M, P) = miis()
	to = [[] for _ in range(N)]
	ot = [[] for _ in range(N)]
	edges = []
	for _ in range(M):
		(a, b, c) = miis()
		a -= 1
		b -= 1
		c = -(c - P)
		to[a].append(b)
		ot[b].append(a)
		edges.append((a, b, c))
	reachableFromZero = reachable_nodeset(0, to)
	reachableToN = reachable_nodeset(N - 1, ot)
	ok = reachableFromZero.intersection(reachableToN)
	edges = tuple(((a, b, c) for (a, b, c) in edges if a in ok and b in ok))
	print(bellmanford(N, 0, N - 1, edges))

def __starting_point():
	solve()
__starting_point()


(N, M, P) = map(int, input().split())
ABC = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	ABC.append((a - 1, b - 1, P - c))
inf = float('inf')
d = [inf] * N
d[0] = 0
for i in range(N):
	for (a, b, c) in ABC:
		if d[b] <= d[a] + c:
			continue
		d[b] = d[a] + c
ans = d[N - 1]
for i in range(N):
	for (a, b, c) in ABC:
		if d[b] <= d[a] + c:
			continue
		d[b] = d[a] + c
if ans != d[N - 1]:
	print(-1)
else:
	print(max(0, -d[N - 1]))


INF = float('inf')

def main():
	(n, m, p) = map(int, input().split())
	es = []
	for _ in range(m):
		e = list(map(int, input().split()))
		es.append([e[0] - 1, e[1] - 1, -e[2] + p])
	v_cost = [INF] * n
	v_cost[0] = 0
	for v in range(n * 2):
		for e in es:
			frm = e[0]
			to = e[1]
			if v_cost[to] > v_cost[frm] + e[2]:
				v_cost[to] = v_cost[frm] + e[2]
				if v >= n:
					v_cost[to] = -INF
		if v == n - 1:
			prev = v_cost[-1]
	if prev != v_cost[-1]:
		return -1
	return max(0, -v_cost[-1])
print(main())


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))
main()


import sys
input = sys.stdin.readline

def BELLMANFORD(point, n, d, p):
	cost = [-float('inf')] * (n + 1)
	cost[point] = 0
	for i in range(n - 1):
		for (nownode, nextnode, c) in d:
			if cost[nextnode] < cost[nownode] + c - p:
				cost[nextnode] = cost[nownode] + c - p
	negative = [0] * (n + 1)
	for i in range(n):
		for (nownode, nextnode, c) in d:
			if negative[nownode] == 1:
				negative[nextnode] = 1
			if cost[nextnode] < cost[nownode] + c - p:
				cost[nextnode] = cost[nownode] + c - p
				negative[nownode] = 1
	return (cost, negative)

def main():
	(n, m, p) = map(int, input().split())
	d = [tuple(map(int, input().split())) for i in [0] * m]
	(x, y) = BELLMANFORD(1, n, d, p)
	if y[n] == 1:
		print(-1)
	else:
		print(max(x[n], 0))
main()


import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, M, P) = lr()
graph = [lr() for _ in range(M)]

def bellmanford(s, g):
	dist = [float('inf')] * (N + 1)
	dist[s] = 0
	for i in range(2 * N):
		for (a, b, c) in graph:
			if dist[b] > dist[a] - c + P:
				dist[b] = dist[a] - c + P
				if i >= N:
					dist[b] = -float('inf')
	if dist[g] == -float('inf'):
		return -1
	else:
		return max(-dist[g], 0)
answer = bellmanford(1, N)
print(answer)


import sys

def main():
	(N, M, P) = map(int, input().split())
	INF = 1e+18
	d = list()
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		d.append((a, b, P - c))
	V = [INF] * N
	V[0] = 0
	for _ in range(N):
		for (s, t, cost) in d:
			if V[s] != INF:
				V[t] = min(V[t], V[s] + cost)
	for _ in range(N):
		for (s, t, cost) in d:
			if V[s] != INF:
				if V[t] > V[s] + cost:
					V[t] = -INF
	if V[-1] == -INF:
		print(-1)
	else:
		print(max(-V[-1], 0))
main()


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
(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 -= p
	c *= -1
	E.append((a, b, c))

def BellmanFord(edges, n, s):
	dist = [inf for i in range(n)]
	dist[s] = 0
	for i in range(n + 10000):
		update = False
		for (u, v, cost) in edges:
			if dist[u] != inf and dist[v] > dist[u] + cost:
				dist[v] = dist[u] + cost
				if i >= n + 5000:
					dist[v] = -inf
				update = True
	return dist
dist = BellmanFord(E, n, 0)
if dist[n - 1] == -inf:
	print(-1)
else:
	print(max(0, -dist[n - 1]))


import sys
sys.setrecursionlimit(10 ** 9)
(N, M, P) = map(int, input().split())
edges = []
to = [[] for i in range(N)]
rto = [[] for i in range(N)]
for i in range(M):
	(u, v, cost) = map(int, input().split())
	u -= 1
	v -= 1
	cost -= P
	cost *= -1
	edges.append([u, v, cost])
	to[u].append(v)
	rto[v].append(u)
canVisitFromS = [False] * N
canVisitFromG = [False] * N

def dfs(u):
	if canVisitFromS[u]:
		return
	canVisitFromS[u] = True
	for v in to[u]:
		dfs(v)

def rdfs(v):
	if canVisitFromG[v]:
		return
	canVisitFromG[v] = True
	for u in rto[v]:
		rdfs(u)
dfs(0)
rdfs(N - 1)
OK = [canVisitFromS[i] * canVisitFromG[i] for i in range(N)]
dist = [float('inf')] * N
dist[0] = 0
ans = 0
step = 0
update = True
while update:
	update = False
	for i in range(M):
		(u, v, cost) = edges[i]
		if OK[u] * OK[v] == 0:
			continue
		if dist[v] > dist[u] + cost:
			dist[v] = dist[u] + cost
			update = True
	step += 1
	if step > N:
		ans = -1
		break
if ans != -1:
	ans = max(0, dist[N - 1] * -1)
print(ans)


def Bellman_Ford(g, start):
	n = len(g)
	dist = [float('inf')] * n
	dist[start] = 0
	a0 = float('inf')
	for i in range(n << 1):
		updated = False
		for v in range(n):
			for (to, cost) in g[v]:
				if dist[to] <= dist[v] + cost:
					continue
				dist[to] = dist[v] + cost
				updated = True
		if not updated:
			break
		if i <= n:
			a0 = dist[-1]
	if a0 != dist[-1]:
		return (None, False)
	return (dist, True)
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(n, m, p) = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
	(a, b, c) = [int(i) for i in readline().split()]
	g[a - 1].append((b - 1, -c + p))
(dist, TF) = Bellman_Ford(g, 0)
if TF:
	print(max(-dist[-1], 0))
else:
	print(-1)


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)
main()


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

def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source] = 0
	for i in range(num_v - 1):
		for edge in edges:
			if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
				if i == num_v - 1:
					return -1
	negative = [False] * n
	for i in range(num_v):
		for edge in edges:
			if negative[edge[0]]:
				negative[edge[1]] = True
			if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				negative[edge[1]] = True
	return (dist[n - 1], negative[n - 1])
(d, n) = BellmanFord(e, n, 0)
if n:
	print(-1)
else:
	print(max(0, -d))


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))


((n, m, p), *l) = [list(map(int, s.split())) for s in open(0)]
I = float('inf')
d = [0] * 2 + [I] * n
for i in range(n * 2):
	for (a, b, c) in l:
		if d[b] > d[a] - c + p:
			d[b] = [d[a] - c + p, -I][i > n]
	if i == n:
		x = d[n]
print([max(-x, 0), -1][d[n] != x])


import sys
sys.setrecursionlimit(100000000)
(n, m, p) = map(int, input().split())
routes = []
bt = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b, c) = map(int, sys.stdin.readline().split())
	routes.append([a, b, -1 * (c - p)])
	bt[b].append(a)
enable = set()
enable.add(n)
for i in range(n):
	for j in range(1, n + 1):
		if j in enable:
			for k in bt[j]:
				if not k in enable:
					enable.add(k)
inf = float('inf')
costs = [inf for _ in range(n + 1)]
costs[1] = 0
error = False
for i in range(n):
	for route in routes:
		if route[1] in enable and costs[route[0]] + route[2] < costs[route[1]]:
			costs[route[1]] = costs[route[0]] + route[2]
			if i == n - 1:
				error = True
				break
if error == True:
	print(-1)
else:
	print(max(0, -1 * costs[n]))


def main():
	INF = float('inf')
	(N, M, P, *ABC) = list(map(int, open(0).read().split()))
	F = [[] for _ in range(N)]
	B = [[] for _ in range(N)]
	E = [(a - 1, b - 1, P - c) for (a, b, c) in zip(*[iter(ABC)] * 3)]
	for (a, b, c) in E:
		F[a].append(b)
		B[b].append(a)
	S = {0}
	stack = [0]
	while stack:
		s = stack.pop()
		for v in F[s]:
			if v not in S:
				stack.append(v)
				S.add(v)
	T = {N - 1}
	stack = [N - 1]
	while stack:
		s = stack.pop()
		for v in B[s]:
			if v not in T:
				stack.append(v)
				T.add(v)
	ok = S & T
	E = [(a, b, c) for (a, b, c) in E if a in ok and b in ok]
	D = [INF] * N
	D[0] = 0

	def bellman_ford(N):
		for _ in range(N):
			update = False
			for (a, b, c) in E:
				if D[b] > D[a] + c:
					D[b] = D[a] + c
					update = True
			if not update:
				return False
		return True
	bellman_ford(N)
	print(-1 if bellman_ford(1) else max(-D[-1], 0))

def __starting_point():
	main()
__starting_point()


(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))


import sys
sys.setrecursionlimit(200000)
(N, M, P) = map(int, input().split())
lis = [[] for i in range(N)]
rev = [[] for i in range(N)]
exist = [False] * N
for i in range(M):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	lis[A].append([B, C - P])
	rev[B].append(A)

def dfs(v):
	exist[v] = True
	for nex in rev[v]:
		if not exist[nex]:
			dfs(nex)
dfs(N - 1)
dis = [float('-inf')] * N
dis[0] = 0
for i in range(N + 1):
	flag = False
	for v in range(N):
		for uc in lis[v]:
			if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
				dis[uc[0]] = dis[v] + uc[1]
				flag = True
if flag:
	print(-1)
else:
	print(max(0, dis[N - 1]))


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)


from collections import deque
(N, M, P) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
to = [False] * (N + 1)
to[1] = True
q = deque([1])
while q:
	u = q.popleft()
	for (a, b, c) in X:
		if a == u and (not to[b]):
			to[b] = True
			q.append(b)
ot = [False] * (N + 1)
ot[N] = True
q = deque([N])
while q:
	u = q.popleft()
	for (a, b, c) in X:
		if b == u and (not ot[a]):
			ot[a] = True
			q.append(a)
INF = 10 ** 9 + 7
start = 1
d = [INF] * (N + 1)
d[start] = 0
updated = True
cnt = 0
while updated and cnt <= M:
	updated = False
	cnt += 1
	for (u, v, c) in X:
		if not to[u] or not ot[u] or (not to[v]) or (not ot[v]):
			continue
		if d[v] > d[u] - (c - P):
			d[v] = d[u] - (c - P)
			updated = True
if cnt > N:
	print(-1)
else:
	print(max(0, -d[-1]))


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


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)


(N, M, P) = map(int, input().split())
edge = []
for i in range(M):
	(A, B, C) = map(int, input().split())
	edge.append((A, B, P - C))
inf = float('inf')
cost = [inf] * (N + 1)
cost[1] = 0
for i in range(N - 1):
	for e in edge:
		(a, b, c) = e
		if cost[a] + c < cost[b]:
			cost[b] = cost[a] + c
for i in range(N):
	for e in edge:
		(a, b, c) = e
		if cost[a] + c < cost[b]:
			if b == N:
				print(-1)
				exit()
			else:
				cost[b] = cost[a] + c
print(max(-cost[N], 0))


def BF(edges, n, s):
	inf = float('inf')
	d = [inf for i in range(n + 1)]
	d[s] = 0
	flag = False
	for i in range(n + 1):
		for (v, u, cost) in edges:
			if d[v] != inf and d[u] > d[v] + cost:
				d[u] = d[v] + cost
	ans1 = d[-1]
	for i in range(n + 1):
		for (v, u, cost) in edges:
			if d[v] != inf and d[u] > d[v] + cost:
				d[u] = d[v] + cost
	ans2 = d[-1]
	if ans2 < ans1:
		return -1
	else:
		return max(-ans1, 0)
(n, m, p) = map(int, input().split())
g = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	g.append([a, b, -(c - p)])
ans = BF(g, n, 1)
print(ans)


import sys

def reverse_search(n, parents):
	q = [n - 1]
	visited = set()
	while q:
		v = q.pop()
		if v in visited:
			continue
		visited.add(v)
		q.extend((u for u in parents[v] if u not in visited))
	return visited
(n, m, p) = list(map(int, input().split()))
INF = 10 ** 12
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
for line in sys.stdin:
	(a, b, c) = map(int, line.split())
	a -= 1
	b -= 1
	links[a].add((b, p - c))
	parents[b].add(a)
reachable = reverse_search(n, parents)
dist = [INF] * n
dist[0] = 0
for _ in range(len(reachable)):
	updated = False
	for v in reachable:
		d = dist[v]
		if d == INF:
			continue
		for (u, c) in links[v]:
			if dist[u] > d + c:
				dist[u] = d + c
				updated = True
	if not updated:
		break
else:
	print(-1)
	exit()
print(max(0, -dist[n - 1]))


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


(N, M, P) = map(int, input().split())
Edges = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	Edges.append([a, b, -(c - P)])
dist = [float('inf')] * N
dist[0] = 0
for i in range(2 * N):
	for (fr, to, cost) in Edges:
		if dist[to] > dist[fr] + cost:
			dist[to] = dist[fr] + cost
			if i >= N:
				dist[to] = -float('inf')
print(max(0, -dist[N - 1]) if -dist[N - 1] != float('inf') else -1)


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)


((N, M, P), *E) = [list(map(int, s.split())) for s in open(0).readlines()]
D = [0] * 2 + [-9000000000.0] * N

def f():
	for _ in D:
		for (a, b, c) in E:
			D[b] = max(D[b], D[a] + c - P)
	return D[N]
s = f()
print([max(s, 0), -1][s < f()])


import sys
inf = 10000000000

def BellmanFord(edges, points, start):
	dist = [inf for i in range(points)]
	dist[start - 1] = 0
	for i in range(points):
		for edge in edges:
			if dist[edge[0] - 1] != inf and dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
		dist1 = dist[N - 1]
	for i in range(points):
		for edge in edges:
			if dist[edge[0] - 1] != inf and dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
		dist2 = dist[N - 1]
	if dist1 != dist2:
		return 'Loop'
	return dist
(N, M, P) = [int(i) for i in input().split()]
Edges = []
for i in range(M):
	(a, b, c) = [int(i) for i in input().split()]
	Edges.append((a, b, P - c))
dist = BellmanFord(Edges, N, 1)
if dist == 'Loop':
	print(-1)
else:
	print(max(-dist[N - 1], 0))


def main():

	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
	(n, m, p, *t) = map(int, open(0).read().split())
	edge = [[] for _ in range(n)]
	edge_rev = [[] for _ in range(n)]
	e = []
	for (a, b, c) in zip(t[::3], t[1::3], t[2::3]):
		edge[a - 1].append(b - 1)
		edge_rev[b - 1].append(a - 1)
		e.append((a - 1, b - 1, p - c))
	use = dfs(edge, 0) & dfs(edge_rev, n - 1)
	e = [(a, b, c) for (a, b, c) in e if a in use and b in use]
	INF = 10 ** 18
	d = [0] + [INF] * (n - 1)
	for _ in range(n):
		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)
		return
	print(max(-d[-1], 0))
main()


import sys

def input():
	return sys.stdin.readline().strip()

def bellman_ford(edges, N, start):
	dist = [float('inf') for _ in range(N)]
	dist[start] = 0
	for i in range(2 * N):
		for (fro, to, cost) in edges:
			if dist[to] > dist[fro] - cost:
				dist[to] = dist[fro] - cost
				if i == N - 1:
					dist[to] = -float('inf')
	return dist

def main():
	(N, M, P) = map(int, input().split())
	edge = []
	for _ in range(M):
		(A, B, C) = map(int, input().split())
		edge.append((A - 1, B - 1, C - P))
	dist = bellman_ford(edge, N, 0)
	if dist[-1] == -float('inf'):
		print(-1)
	elif dist[-1] > 0:
		print(0)
	else:
		print(-1 * dist[-1])
main()


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

def bellman_ford(s, g):
	dist = [float('inf')] * n
	dist[s] = 0
	for i in range(2 * n):
		for (a, b, c) in abc:
			a -= 1
			b -= 1
			cost = -(c - p)
			if dist[b] > dist[a] + cost:
				dist[b] = dist[a] + cost
				if i >= n:
					dist[b] = -float('inf')
	if dist[g] == -float('inf'):
		return -1
	else:
		return max(-dist[g], 0)
ans = bellman_ford(0, n - 1)
print(ans)


import sys
sys.setrecursionlimit(10000000)

def input():
	return sys.stdin.readline()[:-1]
f_inf = float('inf')
(N, M, P) = map(int, input().split())
ABC_d = {}
for m in range(M):
	(A, B, C) = map(int, input().split())
	if A in ABC_d:
		ABC_d[A].append((B, C - P))
	else:
		ABC_d[A] = [(B, C - P)]
cost = [-f_inf] * N
cost[0] = 0
max_num_sum = N * (N + 1) // 2

def solve(pos, cnt, num_sum):
	global cost
	if not pos in ABC_d:
		return
	if cnt > N or num_sum > max_num_sum:
		cost[pos - 1] = f_inf
	for (B, C) in ABC_d[pos]:
		if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
			pass
		elif cost[B - 1] < cost[pos - 1] + C:
			cost[B - 1] = cost[pos - 1] + C
			solve(B, cnt + 1, num_sum + B)
solve(1, 1, 1)
if cost[-1] == f_inf:
	print(-1)
else:
	print(max(0, int(cost[-1])))


from collections import deque
(N, M, P, *L) = map(int, open(0).read().split())
INF = 10 ** 9
Els = []
dic = [[] for i in range(N + 1)]
rdic = [[] for i in range(N + 1)]
for (a, b, c) in zip(*[iter(L)] * 3):
	dic[a].append((b, c - P))
	rdic[b].append((a, c - P))
	Els.append((a, b, -c + P))
ok1 = [False] * (N + 1)
ok1[1] = True
q = deque([1])
while q:
	v = q.popleft()
	for (p, c) in dic[v]:
		if not ok1[p]:
			ok1[p] = True
			q.append(p)
ok2 = [False] * (N + 1)
ok2[N] = True
q = deque([N])
while q:
	v = q.popleft()
	for (p, c) in rdic[v]:
		if not ok2[p]:
			ok2[p] = True
			q.append(p)
ok = [a & b for (a, b) in zip(ok1, ok2)]
dist = [INF] * (N + 1)
dist[1] = 0
cnt = 0
while True:
	end = True
	for (a, b, c) in Els:
		if ok[a] and ok[b] and (dist[a] != INF) and (dist[b] > dist[a] + c):
			end = False
			dist[b] = dist[a] + c
	if end:
		print(max(0, -dist[N]))
		break
	cnt += 1
	if cnt > N:
		print(-1)
		break


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

def bellman_ford(v, s, t, e):
	d = [10 ** 18] * 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:
		return -1
	return max(-d[t], 0)

def main():
	import sys
	input = sys.stdin.readline
	(n, m, p) = map(int, input().split())
	edge = [[] for _ in range(n)]
	edge_rev = [[] for _ in range(n)]
	e = []
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		edge[a - 1].append(b - 1)
		edge_rev[b - 1].append(a - 1)
		e.append((a - 1, b - 1, p - c))
	use = dfs(edge, 0) & dfs(edge_rev, n - 1)
	e = [(a, b, c) for (a, b, c) in e if a in use and b in use]
	print(bellman_ford(n, 0, n - 1, e))

def __starting_point():
	main()
__starting_point()


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))


import sys
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def input():
	return sys.stdin.readline().strip()

def bellman_ford(edges, n_nodes, start, goal):
	dist = [float('inf') for _ in range(n_nodes)]
	dist[start] = 0
	for i in range(2 * n_nodes):
		for (fro, to, cost) in edges:
			if dist[to] > dist[fro] + cost:
				dist[to] = dist[fro] + cost
				if i == n_nodes - 1:
					dist[to] = -float('inf')
	return -dist[goal]

def main():
	(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))
	ans = bellman_ford(edges, N, 0, N - 1)
	if ans == float('inf'):
		print(-1)
	else:
		print(max(ans, 0))
main()


import sys
sys.setrecursionlimit(10 ** 9)

def BF(edges, n, s):
	inf = float('inf')
	d = [inf for i in range(n + 1)]
	d[s] = 0
	update = True
	for i in range(n + 1):
		update = False
		for (v, u, cost) in edges:
			if cand[v] != 1 or cand[u] != 1:
				continue
			if d[v] != inf and d[u] > d[v] + cost:
				d[u] = d[v] + cost
				update = True
		if update == False:
			break
		if i == n:
			return inf
	return -d[-1]

def DFS_1toN(v):
	for u in to[v]:
		if toflag[u] == 0:
			toflag[u] = 1
			DFS_1toN(u)

def DFS_Nto1(v):
	for u in ot[v]:
		if otflag[u] == 0:
			otflag[u] = 1
			DFS_Nto1(u)
(n, m, p) = map(int, input().split())
g = []
to = [[] for _ in range(n + 1)]
ot = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	g.append([a, b, -(c - p)])
	to[a].append(b)
	ot[b].append(a)
toflag = [0] * (n + 1)
toflag[1] = 1
DFS_1toN(1)
otflag = [0] * (n + 1)
otflag[n] = 1
DFS_Nto1(n)
cand = [0] * (n + 1)
for i in range(1, n + 1):
	cand[i] = toflag[i] * otflag[i]
ans = BF(g, n, 1)
if ans == float('inf'):
	print(-1)
else:
	print(max(ans, 0))


import sys
from collections import deque
input = sys.stdin.readline

class Bellman_Ford:

	def __init__(self, v=None, e=None, lis=None, start=None, end=None, inf=float('inf')):
		self.V = v
		self.E = e
		self.lis = lis
		self.start = start if start else 0
		self.end = end if end else self.V - 1
		self.inf = inf
		self.close_minus = False

	def getlist(self, lis):
		self.lis = lis

	def def_start(self, s):
		self.start = s

	def def_end(self, e):
		self.end = e

	def def_inf(self, inf):
		self.inf = inf

	def def_vertice(self, v):
		self.V = v

	def def_edge(self, e):
		self.E = e

	def prepare(self):
		self.cost = [self.inf] * self.V
		self.cost[self.start] = 0

	def search(self):
		for i in range(self.V):
			update = False
			for (x, y, z) in self.lis:
				if self.cost[y] > self.cost[x] + z:
					self.cost[y] = self.cost[x] + z
					update = True
			if not update:
				break
			if i == self.V - 1:
				self.close_minus = True
				return False
		return True

	def main(self):
		self.prepare()
		self.search()

	def cost_all(self):
		return self.cost

def main():
	(n, m, p) = map(int, input().split())
	graph = [None] * m
	tree_forth = [[] for _ in range(n)]
	tree_back = [[] for _ in range(n)]
	for i in range(m):
		(a, b, c) = map(int, input().split())
		tree_forth[a - 1].append(b - 1)
		tree_back[b - 1].append(a - 1)
		c = p - c
		graph[i] = (a - 1, b - 1, c)
	(already1, already2) = ([True] * n, [True] * n)
	for (already, tree, start) in zip([already1, already2], [tree_forth, tree_back], [0, n - 1]):
		not_yet = deque([start])
		already[start] = False
		while not_yet:
			key = not_yet.pop()
			for v in tree[key]:
				if already[v] == False:
					continue
				already[v] = False
				not_yet.append(v)
	graph_new = []
	for i in range(m):
		(a, b, c) = graph[i]
		if already1[a] or already1[b] or already2[a] or already2[b]:
			continue
		graph_new.append((a, b, c))
	bf = Bellman_Ford(v=n, e=m, lis=graph_new)
	bf.main()
	if bf.close_minus:
		print(-1)
	else:
		print(max(0, -bf.cost[n - 1]))

def __starting_point():
	main()
__starting_point()


INF = float('inf')
(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))
d = [-INF] * N
d[0] = 0
for i in range(N - 1):
	for (a, b, c) in edge:
		if d[b] < d[a] + c:
			d[b] = d[a] + c
ans = d[-1]
for i in range(N - 1):
	for (a, b, c) in edge:
		if d[b] < d[a] + c:
			d[b] = INF
if ans != d[-1]:
	print(-1)
else:
	print(max(0, d[N - 1]))


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, M, P, *ABC) = map(int, read().split())
	edge = [0] * M
	for (i, (a, b, c)) in enumerate(zip(*[iter(ABC)] * 3)):
		edge[i] = (a - 1, b - 1, -(c - P))
	dist = [INF] * N
	dist[0] = 0
	for _ in range(N - 1):
		for (a, b, c) in edge:
			if dist[a] != INF and dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
	updated = [False] * N
	for _ in range(N):
		for (a, b, c) in edge:
			if dist[b] != INF and dist[b] > dist[a] + c:
				updated[b] = True
			if updated[a]:
				updated[b] = True
	if updated[N - 1]:
		print(-1)
	else:
		print(max(0, -dist[N - 1]))
	return
main()


INF = float('inf')

def bellman_ford(edges, n, s):
	d = [0] + [INF] * (n - 1)
	for i in range(n):
		for (f, t, c) in edges:
			if d[f] == INF:
				continue
			if d[t] > d[f] + c:
				if i == n - 1:
					d[t] = -INF
				else:
					d[t] = d[f] + c
	for i in range(n):
		for (f, t, c) in edges:
			if d[f] == INF:
				continue
			d[t] = min(d[t], d[f] + c)
	return d
(n, m, p) = map(int, input().split())
es = [None] * m
for i in range(m):
	(f, t, c) = map(int, input().split())
	es[i] = (f - 1, t - 1, -(c - p))
d = bellman_ford(es, n, 0)
print(-1 if d[n - 1] == -INF else max(0, -d[n - 1]))


INF = 10 ** 18

def bellman_ford(s, n, g):
	d = [INF] * n
	d[s] = 0
	for i in range(n - 1):
		update = False
		for (v_from, v_to, cost) in g:
			if d[v_from] != INF and d[v_to] > d[v_from] + cost:
				d[v_to] = d[v_from] + cost
				update = True
		if not update:
			break
	for i in range(n - 1):
		update = False
		for (v_from, v_to, cost) in g:
			if d[v_from] != INF and d[v_to] > d[v_from] + cost:
				d[v_to] = -INF
				update = True
		if not update:
			break
	return d
(n, m, p) = map(int, input().split())
g = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	c -= p
	g.append((a - 1, b - 1, -c))
d = bellman_ford(0, n, g)
if d[-1] == -INF:
	print(-1)
else:
	ans = -d[-1]
	ans = max(0, ans)
	print(ans)


(n, m, p) = map(int, input().split())
abc = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	abc.append([a - 1, b - 1, p - c])
d = [float('inf')] * n
d[0] = 0
for i in range(n):
	for (a, b, c) in abc:
		d[b] = min(d[b], d[a] + c)
for (a, b, c) in abc:
	if d[b] > d[a] + c:
		d[b] = -float('inf')
for i in range(n):
	for (a, b, c) in abc:
		d[b] = min(d[b], d[a] + c)
if d[n - 1] == -float('inf'):
	print(-1)
else:
	print(max(0, -d[n - 1]))


(N, M, P) = map(int, input().split())
edges = []
edges1 = [[] for _ in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	edges1[b - 1].append(a - 1)
	edges.append((a - 1, b - 1, -c + P))
from collections import deque
que = deque([N - 1])
flag = [True] * N
flag[-1] = False
while que:
	v = que.pop()
	for e in edges1[v]:
		if flag[e]:
			que.append(e)
			flag[e] = False

def f(n, w, es):
	d = [float('inf')] * n
	d[0] = 0
	for i in range(n):
		for j in range(w):
			e = es[j]
			if flag[e[1]]:
				continue
			if d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				if i == n - 1:
					return False
	return d
d = f(N, M, edges)
if d:
	print(max(-d[-1], 0))
else:
	print(-1)


import sys
from collections import deque
import heapq

def solve():
	input = sys.stdin.readline
	(N, M, P) = map(int, input().split())
	graph = [None for i in range(M)]
	for i in range(M):
		(a, b, c) = map(int, input().split())
		graph[i] = (a - 1, b - 1, P - c)
	gain = [10 ** 20 for i in range(N)]
	gain[0] = 0
	for i in range(N):
		update = False
		for (efrom, eto, ecost) in graph:
			if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
				gain[eto] = gain[efrom] + ecost
				update = True
		if not update:
			print(max(-gain[N - 1], 0))
			break
	else:
		possible_min = gain[N - 1]
		for i in range(N):
			for (efrom, eto, ecost) in graph:
				if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
					gain[eto] = gain[efrom] + ecost
		if gain[N - 1] == possible_min:
			print(max(-gain[N - 1], 0))
		else:
			print(-1)
	return 0
solve()


import sys
INF = 10 ** 9
(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, P - C])
flag1 = [0] * N
flag2 = [0] * N
flag = [0] * N
flag1[0] = 1
flag2[N - 1] = 1
for i in range(N - 1):
	for j in range(M):
		edge = edges[j]
		if flag1[edge[0]]:
			flag1[edge[1]] = 1
		if flag2[edge[1]]:
			flag2[edge[0]] = 1
for i in range(N):
	if flag1[i] and flag2[i]:
		flag[i] = 1
d = [INF] * N
d[0] = 0
k = None
for i in range(N):
	for j in range(M):
		edge = edges[j]
		if d[edge[1]] > d[edge[0]] + edge[2]:
			d[edge[1]] = d[edge[0]] + edge[2]
			if i == N - 1 and flag[edge[1]]:
				print(-1)
				sys.exit()
print(max(-1 * d[N - 1], 0))


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]))


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:
					before_dist = dist[num_v - 1]
					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 before_dist != dist[num_v - 1]:
						return -1
	return dist
(N, M, P) = map(int, input().split())
edges = []
for m in range(M):
	(A, B, C) = map(int, input().split())
	edges.append([A, B, -(C - P)])
dist = BellmanFord(edges, N, 1)
if dist == -1:
	print(-1)
else:
	print(max(-dist[N - 1], 0))


(N, M, P) = map(int, input().split())
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a, b, c - P))
INF = float('inf')
coin_map = [-INF] * (N + 1)
coin_map[1] = 0
for i in range(2 * N):
	for (a, b, c) in edges:
		if coin_map[b] < coin_map[a] + c:
			coin_map[b] = coin_map[a] + c
			if i >= N:
				coin_map[b] = INF
	if i == N - 1:
		ans = coin_map[N]
if ans != coin_map[N]:
	print(-1)
else:
	print(max(0, coin_map[N]))


inf = 10 ** 18
(n, m, p) = map(int, input().split())
edge = []
d = [inf] * n
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c = p - c
	edge.append((a, b, c))
d[0] = 0
for i in range(n - 1):
	pre = d[n - 1]
	for (a, b, c) in edge:
		if d[a] != inf and d[b] > d[a] + c:
			d[b] = d[a] + c
			update = True
pre = d[n - 1]
for i in range(n - 1):
	for (a, b, c) in edge:
		if d[a] != inf and d[b] > d[a] + c:
			d[b] = d[a] + c
if pre != d[n - 1]:
	print(-1)
else:
	print(max(0, -d[n - 1]))


def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source - 1] = 0
	flag = False
	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:
					if edge[1] == num_v:
						return -1
					else:
						dist[edge[1] - 1] = -inf
						flag = True
	if flag:
		for i in range(num_v):
			for edge in edges:
				if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
					dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
					if edge[1] == num_v:
						return -1
	return dist
(N, M, P) = [int(x) for x in input().split()]
gp = []
for _ in range(M):
	(A, B, C) = [int(x) for x in input().split()]
	gp.append([A, B, P - C])
li = BellmanFord(gp, N, 1)
if li == -1:
	print(-1)
else:
	print(max(0, -li[N - 1]))


(N, M, P) = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
	for (a, b, c) in E:
		if D[a] == None:
			continue
		if D[b] == None:
			D[b] = D[a] + c - P
		else:
			D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
	for (a, b, c) in E:
		if D[a] == None:
			continue
		if D[b] == None:
			D[b] = D[a] + c - P
		else:
			D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
	print(-1)
else:
	print(max(D[-1], 0))


((n, m, p), *l) = [list(map(int, s.split())) for s in open(0)]
d = [0] * 2 + [9e+99] * n
for i in range(n * 2):
	for (a, b, c) in l:
		if d[b] > d[a] - c + p:
			d[b] = [d[a] - c + p, -9e+99][i > n]
	if i == n:
		x = d[n]
print([max(-x, 0), -1][d[n] != x])


(n, m, p) = map(int, input().split())
edge = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edge.append([a - 1, b - 1, -c])
d = [float('inf') for _ in range(n)]
d[0] = 0
for i in range(n * 2):
	for (now, next, weight) in edge:
		if d[next] > d[now] + weight + p:
			d[next] = d[now] + weight + p
			if i > n - 1:
				d[next] = -float('inf')
		if i == n - 1:
			prev = d[-1]
if prev != d[-1]:
	print('-1')
else:
	print(max(-prev, 0))


from collections import deque

def solve():
	(N, M, P) = map(int, input().split())
	G = [[] for i in range(N)]
	RG = [[] for i in range(N)]
	for i in range(M):
		(a, b, c) = map(int, input().split())
		G[a - 1].append((b - 1, P - c))
		RG[b - 1].append((a - 1, P - c))

	def chk(s, G):
		P = [0] * N
		que = deque([s])
		used = [0] * N
		used[s] = 1
		while que:
			v = que.popleft()
			P[v] = 1
			for (w, c) in G[v]:
				if used[w]:
					continue
				que.append(w)
				used[w] = 1
		return P
	P0 = chk(0, G)
	P1 = chk(N - 1, RG)
	F = [P0[i] == P1[i] == 1 for i in range(N)]
	I = [i for i in range(N) if F[i]]
	E0 = []
	for v in I:
		for (w, c) in G[v]:
			if not F[w]:
				continue
			E0.append((v, w, c))
	dist = [10 ** 18] * N
	dist[0] = 0
	L = len(I)
	for i in range(L):
		update = 0
		for (v, w, c) in E0:
			x = c + dist[v]
			if x < dist[w]:
				dist[w] = x
				update = 1
		if not update:
			break
	else:
		print('-1')
		return
	print(max(-dist[N - 1], 0))
solve()


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(u):
	ok[u] = 1
	for v in to[u]:
		if ok[v]:
			continue
		dfs(v)

def rdfs(u):
	ok[u] += 2
	for v in fr[u]:
		if ok[v] > 1:
			continue
		rdfs(v)
inf = 10 ** 9
to = defaultdict(list)
fr = defaultdict(list)
abc = []
(n, m, p) = map(int, input().split())
ok = [0] * n
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c = -(c - p)
	to[a].append(b)
	fr[b].append(a)
	abc.append([a, b, c])
dfs(0)
rdfs(n - 1)
score = [inf] * n
score[0] = 0
for i in range(n):
	stop = True
	for (a, b, c) in abc:
		if ok[a] < 3 or ok[b] < 3:
			continue
		tmp = score[a] + c
		if tmp < score[b]:
			score[b] = tmp
			stop = False
	if stop:
		print(max(0, -score[n - 1]))
		break
else:
	print(-1)


(N, M, P) = map(int, input().split())
adj = [list() for _ in range(N)]
inv = [list() for _ in range(N)]
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	inv[b - 1].append(a - 1)
	adj[a - 1].append(b - 1)
	edges.append((a - 1, b - 1, P - c))
stack = [N - 1]
reachable1 = {N - 1}
while stack:
	v = stack.pop()
	for u in inv[v]:
		if u not in reachable1:
			stack.append(u)
			reachable1.add(u)
stack = [0]
reachable2 = {0}
while stack:
	v = stack.pop()
	for u in adj[v]:
		if u not in reachable2:
			stack.append(u)
			reachable2.add(u)
reachable = reachable1 & reachable2
edges = [(a, b, w) for (a, b, w) in edges if a in reachable and b in reachable]
dist = [float('inf')] * N
dist[0] = 0
for i in range(len(reachable) - 1):
	for (a, b, w) in edges:
		dist[b] = min(dist[a] + w, dist[b])
for (a, b, w) in edges:
	if dist[b] > dist[a] + w:
		print(-1)
		break
else:
	print(max(0, -dist[-1]))


import time
t1 = time.time()
(N, M, P) = list(map(int, input().split()))
ABC = [tuple(map(int, input().split())) for _ in range(M)]
to_w = [set() for _ in range(N)]
for (a, b, c) in ABC:
	to_w[a - 1].add((b - 1, P - c))
reachable_from_start = {0}
q = {0}
while q:
	u = q.pop()
	for (v, _) in to_w[u]:
		if v not in reachable_from_start:
			reachable_from_start.add(v)
			q.add(v)
from_w = [set() for _ in range(N)]
for (a, b, c) in ABC:
	from_w[b - 1].add((a - 1, P - c))
reachable_to_goal = {N - 1}
q = {N - 1}
while q:
	u = q.pop()
	for (v, _) in from_w[u]:
		if v not in reachable_to_goal:
			reachable_to_goal.add(v)
			q.add(v)
reachable = reachable_from_start & reachable_to_goal
to_w = [set() for _ in range(N)]
for (a, b, c) in ABC:
	if a - 1 in reachable and b - 1 in reachable:
		to_w[a - 1].add((b - 1, P - c))
d = [float('inf')] * N
d[0] = 0
q = {0}
while q:
	u = q.pop()
	for (v, w) in to_w[u]:
		tmp = d[u] + w
		if tmp < d[v]:
			d[v] = tmp
			if v not in q:
				q.add(v)
		if time.time() > 1.9 + t1:
			d[-1] = -float('inf')
			break
	else:
		continue
	break
if d[-1] == -float('inf'):
	print(-1)
else:
	print(max(0, -d[-1]))


import sys
input = sys.stdin.buffer.readline

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

	def BellmanFord(edges, v, source):
		INF = float('inf')
		dist = [INF for _ in range(v)]
		dist[source] = 0
		for i in range(2 * v + 1):
			for (now, fol, cost) in edges:
				if dist[now] != INF and dist[fol] > dist[now] + cost:
					dist[fol] = dist[now] + cost
					if i >= v:
						dist[fol] = -INF
		if dist[v - 1] == -INF:
			return -1
		else:
			return max(0, -1 * dist[v - 1])
	edges = []
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		edges.append((a - 1, b - 1, P - c))
	print(BellmanFord(edges, N, 0))
main()


def BF(p, n, s):
	inf = float('inf')
	d = [inf for i in range(n)]
	d[s - 1] = 0
	for i in range(n + 1):
		for e in p:
			if e[0] != inf and d[e[1] - 1] > d[e[0] - 1] + e[2]:
				d[e[1] - 1] = d[e[0] - 1] + e[2]
	ans1 = d[-1]
	for i in range(n + 1):
		for e in p:
			if e[0] != inf and d[e[1] - 1] > d[e[0] - 1] + e[2]:
				d[e[1] - 1] = d[e[0] - 1] + e[2]
	ans2 = d[-1]
	if ans1 > ans2:
		return ['inf']
	else:
		return [-ans1]
(n, m, p) = map(int, input().split())
g = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	g.append([a, b, -(c - p)])
g.append([n, n + 1, 0])
ans = BF(g, n + 1, 1)[-1]
if ans == 'inf':
	print(-1)
else:
	print(max(ans, 0))


import sys
from collections import deque

def dfs(x, s):
	used = {s}
	search = deque([s])
	while search:
		ss = search.pop()
		for sss in x[ss]:
			if sss in used:
				continue
			used.add(sss)
			search.append(sss)
	return used

def bellmanford(edges):
	coins = [-float('inf')] * N
	coins[0] = 0
	for _ in range(N):
		f = True
		for (u, v, c) in edges:
			if coins[u] + c > coins[v]:
				coins[v] = coins[u] + c
				f = False
		if f:
			return max(0, coins[-1])
	return -1
(N, M, P) = map(int, input().split())
ABC = []
Adake = [[] for _ in range(N)]
Bdake = [[] for _ in range(N)]
for _ in range(M):
	(A, B, C) = map(int, input().split())
	ABC.append((A - 1, B - 1, C - P))
	Adake[A - 1].append(B - 1)
	Bdake[B - 1].append(A - 1)
U = dfs(Adake, 0) & dfs(Bdake, N - 1)
ABC = [(a, b, c) for (a, b, c) in ABC if a in U and b in U]
print(bellmanford(ABC))


(N, M, P) = map(int, input().split())
E = dict()
for i in range(M):
	(a, b, c) = map(int, input().split())
	E[i, a, b] = c - P
INF = float('inf')
dist = {i: -INF for i in range(1, N + 1)}
dist[1] = 0
ans = 0
for i in range(N * 2):
	for (iuv, c) in E.items():
		(_, u, v) = iuv
		if dist[v] < dist[u] + c:
			dist[v] = dist[u] + c
			if i >= N:
				dist[v] = INF
	if i == N - 1:
		ans = dist[N]
print(max(0, dist[N]) if ans == dist[N] else -1)


(n, m, p) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
distance = [float('inf')] * n
distance[0] = 0
for i in range(n - 1):
	for j in range(m):
		if distance[l[j][1] - 1] > distance[l[j][0] - 1] - l[j][2] + p:
			distance[l[j][1] - 1] = distance[l[j][0] - 1] - l[j][2] + p
x = distance[n - 1]
for i in range(n):
	for j in range(m):
		if distance[l[j][1] - 1] > distance[l[j][0] - 1] - l[j][2] + p:
			distance[l[j][1] - 1] = -float('inf')
if distance[n - 1] != x:
	print(-1)
else:
	print(max(-distance[n - 1], 0))


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))


from collections import deque
import math

def dfs(edges, s):
	stack = deque([s])
	used = {s}
	while stack:
		x = stack.pop()
		for y in edges[x]:
			if y not in used:
				used.add(y)
				stack.append(y)
	return used

def bfs(edges, s):
	queue = deque([s])
	used = {s}
	while queue:
		x = queue.popleft()
		for y in edges[x]:
			if y in used:
				continue
			used.add(y)
			queue.append(y)
	return used

def bellman(dist):
	cost = [float('inf')] * n
	cost[0] = 0
	for _ in range(n):
		updated = False
		for (u, v, c) in dist:
			if cost[u] + c < cost[v]:
				cost[v] = cost[u] + c
				updated = True
	if updated == True:
		return -1
	else:
		return max(0, cost[n - 1] * -1)
(n, m, p) = map(int, input().split())
dist = []
edge1 = [[] for _ in range(n)]
edge2 = [[] for _ in range(n)]
for _ in range(m):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	dist.append((u, v, (c - p) * -1))
	edge1[u].append(v)
	edge2[v].append(u)
use = dfs(edge1, 0) & dfs(edge2, n - 1)
dist2 = [(a, b, c) for (a, b, c) in dist if a in use and b in use]
print(bellman(dist2))


(n, m, p) = map(int, input().split())
edge = []
e1 = [list() for _ in range(n + 1)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edge.append((a, b, p - c))
	e1[a].append(b)
dis = [float('inf')] * (n + 1)
dis[1] = 0
t = []
for i in range(n):
	for (a, b, c) in edge:
		if dis[b] > dis[a] + c:
			dis[b] = dis[a] + c
			if i == n - 1:
				t.append(b)
s = set(t)
while t:
	v = t.pop()
	for x in e1[v]:
		if x == n:
			print(-1)
			exit(0)
		if x in s:
			continue
		s.add(x)
		t.append(x)
print(max(0, -dis[n]))


import sys
input = sys.stdin.readline
from collections import *

def bfs(s, g):
	q = deque([s])
	dist = [-1] * N
	dist[s] = 0
	while q:
		v = q.popleft()
		for nv in g[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist

def bellman_ford():
	dist = [10 ** 18] * N
	dist[0] = 0
	for i in range(N):
		for (s, t, w) in edges:
			if d1[s] == -1 or d2[t] == -1:
				continue
			if dist[t] > dist[s] + w:
				dist[t] = dist[s] + w
				if i == N - 1:
					print(-1)
					exit()
	return -dist[N - 1]
(N, M, P) = map(int, input().split())
G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]
edges = []
for _ in range(M):
	(A, B, C) = map(int, input().split())
	G[A - 1].append(B - 1)
	rG[B - 1].append(A - 1)
	edges.append((A - 1, B - 1, -(C - P)))
d1 = bfs(0, G)
d2 = bfs(N - 1, rG)
print(max(0, bellman_ford()))


(N, M, P) = list(map(int, input().split()))
abc = []
edge = [[] for _ in range(N)]
for _ in range(M):
	(a, b, c) = list(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):
	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_))


def bellman_ford(v, G):
	import copy
	INF = 10 ** 10
	ret = [INF] * len(G)
	ret[v] = 0
	for _ in range(len(G) - 1):
		for (u, g) in enumerate(G):
			for (w, l) in g:
				if not ret[u] == INF and ret[w] > ret[u] + l:
					ret[w] = ret[u] + l
	for _ in range(len(G) - 1):
		for (u, g) in enumerate(G):
			for (w, l) in g:
				if not ret[w] == INF and ret[w] > ret[u] + l:
					ret[w] = -INF
	return ret
(N, M, P) = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
	(A, B, C) = map(int, input().split())
	G[A - 1].append((B - 1, -C + P))
ans = bellman_ford(0, G)[-1]
print('-1' if ans == -10 ** 10 else max(-ans, 0))


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())


(N, M, P) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for _ in range(N)]
bs = [[] for _ in range(N)]
for (a, b, c) in ABC:
	(a, b) = (a - 1, b - 1)
	es[a].append((b, c - P))
	bs[b].append((a, c - P))
go_set = set([0])
stack = [0]
while stack:
	v = stack.pop()
	for (to, _) in es[v]:
		if to in go_set:
			continue
		go_set.add(to)
		stack.append(to)
bk_set = set([N - 1])
stack = [N - 1]
while stack:
	v = stack.pop()
	for (to, _) in bs[v]:
		if to in bk_set:
			continue
		bk_set.add(to)
		stack.append(to)
use = go_set & bk_set
K = len(use)
INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(K):
	for v in range(N):
		if v not in use:
			continue
		for (to, c) in es[v]:
			if to not in use:
				continue
			if d[to] > d[v] - c:
				d[to] = d[v] - c
				if i == K - 1:
					print(-1)
					exit()
print(max(0, -d[-1]))


def validate(paths, start):
	valid_paths = {start}
	stack = [start]
	while stack:
		v = stack.pop()
		if v not in paths:
			continue
		for w in paths[v]:
			if w in valid_paths:
				continue
			valid_paths.add(w)
			stack.append(w)
	return valid_paths

def bellman_ford(edges, num_v, start, end):
	INF = 10 ** 18
	dist = [INF] * num_v
	dist[start] = 0
	for _ in range(num_v):
		updated = False
		for (f, t, c) in edges:
			if dist[f] == INF:
				continue
			cost = dist[f] + c
			if cost < dist[t]:
				dist[t] = cost
				updated = True
		if not updated:
			break
	else:
		return -1
	return max(-dist[end], 0)

def main():
	from collections import defaultdict
	(n, m, p, *tmp) = list(map(int, open(0).read().split()))
	paths_rev = defaultdict(list)
	edges = []
	for (a, b, c) in zip(*[iter(tmp)] * 3):
		paths_rev[b - 1].append(a - 1)
		edges.append((a - 1, b - 1, p - c))
	valid_paths = validate(paths_rev, n - 1)
	edges = [(a, b, c) for (a, b, c) in edges if a in valid_paths and b in valid_paths]
	res = bellman_ford(edges, n, 0, n - 1)
	print(res)

def __starting_point():
	main()
__starting_point()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, m, p) = map(int, input().split())
ns = [[] for _ in range(n)]
rns = [[] for _ in range(n)]
mc = -1
for _ in range(m):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	ns[u].append((p - c, v))
	rns[v].append(u)
q = [n - 1]
seen = [False] * n
seen[n - 1] = True
while q:
	u = q.pop()
	for v in rns[u]:
		if seen[v]:
			continue
		seen[v] = True
		q.append(v)

def bf(start):
	dist = [float('inf')] * n
	dist[start] = 0
	for i in range(n):
		for u in range(n):
			if dist[u] == float('inf'):
				continue
			for (c, v) in ns[u]:
				if dist[v] > dist[u] + c:
					dist[v] = dist[u] + c
					if i >= n - 1 and seen[v]:
						return -1
	return dist
dist = bf(0)
if dist == -1:
	ans = -1
else:
	ans = max(0, dist[n - 1] * -1)
print(ans)


(N, M, P) = map(int, input().split())
ABC = [list(map(int, input().split())) for i in range(M)]
c = [[] for i in range(N)]
v = [0] * N
for (a, b, _) in ABC:
	c[a - 1].append(b - 1)
q = [0]
while q:
	p = q.pop()
	if v[p] == 0:
		v[p] = 1
		for n in c[p]:
			if n != p:
				q.append(n)
inf = 10 ** 20
f = lambda i, j, w: [i - 1, j - 1, P - w]
edge = [f(i, j, w) for (i, j, w) in ABC if v[i - 1]]

def bf(N, s):
	d = [inf] * N
	d[s] = 0
	prev = [-1] * N
	for i in range(N - 1):
		f = 0
		for (i, j, w) in edge:
			if d[j] > d[i] + w:
				d[j] = d[i] + w
				prev[j] = i
				f = 1
		if f == 0:
			break
	while True:
		f = 0
		for (i, j, w) in edge:
			if d[j] > d[i] + w and (d[j] != -inf or d[i] != -inf):
				d[i] = d[j] = -inf
				f = 1
		if f == 0:
			break
	return d
d = bf(N, 0)
print(max(0, -d[-1]) if d[-1] > -inf else -1)


from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError

def reachable_nodes(s, edges):
	cur = {s}
	reachable = set()
	while cur:
		reachable |= cur
		cur = set().union(*(edges[node] for node in cur)) - reachable
	return reachable

def solve():
	(N, M, P) = list(map(int, input().split()))
	(A, B, C) = ([0] * M, [0] * M, [0] * M)
	to = [[] for _ in range(N)]
	reverse_to = [[] for _ in range(N)]
	for i in range(M):
		(a, b, c) = list(map(int, input().split()))
		(A[i], B[i], C[i]) = (a - 1, b - 1, P - c)
		to[a - 1].append(b - 1)
		reverse_to[b - 1].append(a - 1)
	reachable = reachable_nodes(0, to) & reachable_nodes(N - 1, reverse_to)
	edge_dict = dict()
	for (a, b, c) in zip(A, B, C):
		if a in reachable and b in reachable:
			edge_dict[a, b] = min(c, edge_dict.get((a, b), 10 ** 6))
	(AA, BB, CC) = ([], [], [])
	for ((a, b), c) in list(edge_dict.items()):
		AA.append(a)
		BB.append(b)
		CC.append(c)
	graph = csr_matrix((CC, (AA, BB)), shape=(N, N))
	try:
		bf = bellman_ford(graph, indices=[0])
		print(max(0, -int(bf[0][N - 1])))
	except NegativeCycleError:
		print(-1)

def __starting_point():
	solve()
__starting_point()


(N, M, P) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for i in range(M)]
g = [[] for i in range(N)]
revg = [[] for i in range(N)]
for (a, b, _) in ABC:
	(a, b) = (a - 1, b - 1)
	g[a].append(b)
	revg[b].append(a)
st = set([0])
stack = [0]
while stack:
	v = stack.pop()
	for to in g[v]:
		if to in st:
			continue
		st.add(to)
		stack.append(to)
revst = set([N - 1])
stack = [N - 1]
while stack:
	v = stack.pop()
	for to in revg[v]:
		if to in revst:
			continue
		revst.add(to)
		stack.append(to)
use = st & revst
es = []
for (a, b, c) in ABC:
	(a, b) = (a - 1, b - 1)
	if a in use and b in use:
		es.append((a, b, c))
INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
	for (fr, to, c) in es:
		cost = -(c - P)
		if d[to] > d[fr] + cost:
			d[to] = d[fr] + cost
			if i == N - 1:
				print(-1)
				exit()
print(max(0, -d[-1]))


(N, M, P) = map(int, input().split())
E = [list(map(int, input().split())) for _ in range(M)]
A = [-float('inf')] * (N + 1)
A[1] = 0
for v in range(N):
	for (a, b, c) in E:
		t = A[a] + c - P
		if t > A[b]:
			A[b] = t
ans = A[N]
for v in range(N):
	for (a, b, c) in E:
		t = A[a] + c - P
		if t > A[b]:
			A[b] = t
if ans != A[N]:
	print(-1)
else:
	print(max(0, ans))


(n, m, p) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(m)]
INF = float('inf')
dist = [INF] * n
dist[0] = 0
prev = 0
for i in range(2 * n):
	for (fr, to, cost) in E:
		(fr, to) = (fr - 1, to - 1)
		cost *= -1
		cost += p
		if dist[fr] != INF and dist[to] > dist[fr] + cost:
			dist[to] = dist[fr] + cost
			if i >= n:
				dist[to] = -float('inf')
		if i == n - 1:
			prev = dist[n - 1]
if prev == dist[n - 1]:
	print(max(-dist[n - 1], 0))
else:
	print(-1)


inf = float('inf')
(V, E, P) = map(int, input().split())
edge = []
for i in range(E):
	(A, B, C) = map(int, input().split())
	edge.append([A - 1, B - 1, P - C])
d = [inf] * V
d[0] = 0
for i in range(V):
	update = False
	for j in range(E):
		(From, To, cost) = edge[j]
		if d[From] != inf and d[To] > d[From] + cost:
			d[To] = d[From] + cost
			update = True
	if not update:
		break
ans = d[V - 1]
for i in range(V):
	update = False
	for j in range(E):
		(From, To, cost) = edge[j]
		if d[From] != inf and d[To] > d[From] + cost:
			d[To] = d[From] + cost
			update = True
	if not update:
		break
loop = ans != d[V - 1]
if loop:
	print(-1)
else:
	ans = -d[-1]
	print(max(0, ans))


(N, M, P) = map(int, input().split())
edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]
E = []
for _ in range(M):
	(fr, to, c) = map(int, input().split())
	fr -= 1
	to -= 1
	E.append((fr, to, -(c - P)))
	edges[fr].append(to)
	edgesR[to].append(fr)

def dfs(edges, s):
	visited = [False] * N
	st = [s]
	visited[s] = True
	while st:
		for to in edges[st.pop()]:
			if not visited[to]:
				st.append(to)
				visited[to] = True
	return visited
canGo = dfs(edges, 0)
canBack = dfs(edgesR, N - 1)
minDist = [10 ** 18] * N
minDist[0] = 0
for i in range(N + 1):
	for (fr, to, c) in E:
		d = minDist[fr] + c
		if minDist[to] > d:
			if i == N and canGo[fr] and canBack[to]:
				print('-1')
				exit()
			minDist[to] = d
print(max(0, -minDist[N - 1]))


import sys
input = sys.stdin.readline
(n, m, p) = map(int, input().split())
edge = [[] for i in range(m)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	edge[i] = [a - 1, b - 1, -c + p]
d = [float('inf')] * n
d[0] = 0
for _ in range(n):
	for i in range(m):
		(e0, e1, e2) = edge[i]
		d[e1] = min(d[e1], d[e0] + e2)
ans1 = d[-1]
for _ in range(n):
	for i in range(m):
		(e0, e1, e2) = edge[i]
		if d[e1] > d[e0] + e2:
			d[e1] = -float('inf')
ans2 = d[-1]
print(-1 if ans1 != ans2 else max(0, -ans1))


import sys
input = sys.stdin.readline
(n, m, p) = map(int, input().split())
abd = [list(map(int, input().split())) for i in range(m)]
come = [[] for i in range(n + 1)]
for (a, b, d) in abd:
	come[b].append(a)
visitable = [0] * (n + 1)
stack = [n]
visitable[n] = 1
while stack:
	x = stack.pop()
	for y in come[x]:
		if visitable[y] == 0:
			visitable[y] = 1
			stack.append(y)
score = [10 ** 15 for i in range(n + 1)]
score[1] = 0
for j in range(n + 1):
	flg = 0
	for i in range(m):
		(v1, v2, e) = abd[i]
		if visitable[v1] & visitable[v2] == 0:
			continue
		e = -e + p
		if score[v1] != 10 ** 15 and score[v2] > score[v1] + e:
			score[v2] = score[v1] + e
			flg = 1
			if j == n - 1:
				last = score[:]
			if j == n:
				onemore = score[:]
	if flg == 0:
		break
if flg == 0:
	print(max(0, -score[n]))
elif last == onemore:
	print(max(last[n], 0))
else:
	print(-1)


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1

def main():
	(N, M, P) = map(int, input().split())
	edge = []
	for _ in range(M):
		(A, B, C) = map(int1, input().split())
		C += 1
		edge.append((A, B, P - C))
	d = [INF] * N
	d[0] = 0
	f = False
	for i in range(N * 2):
		for (a, b, c) in edge:
			if d[b] > d[a] + c:
				if i < N - 1:
					d[b] = d[a] + c
				else:
					if d[a] < 10 ** 17:
						d[b] = -INF
					if b == N - 1:
						f = True
	if f:
		print(-1)
	else:
		print(max(-d[N - 1], 0))
main()


INF = 10 ** 18
(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))
dist = [INF] * n
dist[0] = 0
update = 1
terminal_update = 0
for _ in range(n * 2):
	update = 0
	for (v, e) in enumerate(edge):
		for (t, cost) in e:
			if dist[v] != INF and dist[v] + cost < dist[t]:
				dist[t] = dist[v] + cost
				update = 1
				if t == n - 1:
					terminal_update += 1
	if not update:
		print(max(0, -dist[n - 1]))
		exit()
else:
	if terminal_update > 1:
		print(-1)
	else:
		print(max(0, -dist[n - 1]))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
(N, M, P) = map(int, input().split())
INF = 1000000000
edge = []
to = [[] for _ in range(N)]
rto = [[] for _ in range(N)]
reachable_from1 = [False] * N
reachable_fromN = [False] * N
for i in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c = -c
	to[a].append(b)
	rto[b].append(a)
	edge.append([a, b, c])

def dfs(v):
	if reachable_from1[v] == True:
		return
	reachable_from1[v] = True
	for u in to[v]:
		dfs(u)

def rdfs(v):
	if reachable_fromN[v] == True:
		return
	reachable_fromN[v] = True
	for u in rto[v]:
		rdfs(u)
dfs(0)
rdfs(N - 1)
ok = [False] * N
for i in range(N):
	ok[i] = reachable_from1[i] & reachable_fromN[i]
d = [INF] * N
d[0] = 0
update = True
step = 0
while update:
	update = False
	for i in range(M):
		(a, b, c) = edge[i]
		if not ok[a]:
			continue
		newD = d[a] + c + P
		if newD < d[b]:
			d[b] = newD
			update = True
	step += 1
	if step > N:
		print(-1)
		sys.exit()
print(max(0, -d[N - 1]))


from collections import deque
import sys
input = sys.stdin.readline

def bellman_ford(N, adj, start):
	ans = [float('inf')] * N
	q = deque()
	q.append((start, 0, 0))
	while len(q):
		(i, cost, path) = q.pop()
		if cost >= ans[i]:
			continue
		ans[i] = cost
		for j in adj[i]:
			ncost = cost + adj[i][j]
			if path > N:
				ncost = -float('inf')
			q.append((j, ncost, path + 1))
	return ans

def main():
	(N, M, P) = map(int, input().split())
	adj = [{} for _ in range(N)]
	for _ in range(M):
		(A, B, C) = map(int, input().split())
		if B - 1 in adj[A - 1]:
			adj[A - 1][B - 1] = min(P - C, adj[A - 1][B - 1])
		else:
			adj[A - 1][B - 1] = P - C
	costs = bellman_ford(N, adj, 0)
	ans = -costs[N - 1]
	if ans < 0:
		print(0)
	elif ans == float('inf'):
		print(-1)
	else:
		print(ans)
main()


from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError

def main():
	(N, M, P) = list(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) = list(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 list(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())


(N, M, P) = map(int, input().split())
edges = []
toE = [[] for _ in range(N)]
frE = [[] for _ in range(N)]
for _ in range(M):
	(fr, to, c) = map(int, input().split())
	fr -= 1
	to -= 1
	edges.append((fr, to, -(c - P)))
	toE[fr].append(to)
	frE[to].append(fr)

def getVisitedList(s, edges):
	visited = [False] * N
	st = [s]
	visited[s] = True
	while st:
		now = st.pop()
		for to in edges[now]:
			if not visited[to]:
				visited[to] = True
				st.append(to)
	return visited
canGo = getVisitedList(0, toE)
canBack = getVisitedList(N - 1, frE)

def sol():
	minDist = [10 ** 18] * N
	minDist[0] = 0
	for i in range(N + 1):
		for (fr, to, c) in edges:
			d = minDist[fr] + c
			if minDist[to] > d:
				if i == N and canGo[fr] and canBack[to]:
					return -1
				minDist[to] = d
	return max(0, -minDist[N - 1])
print(sol())


from collections import deque
(N, M, P) = map(int, input().split())
INF = 10 ** 18
edge = []
rev_edge = [[] for _ in range(N + 1)]
dis = [INF] * (N + 1)
dis[1] = 0
for i in range(M):
	(A, B, C) = map(int, input().split())
	edge.append((A, B, P - C))
	rev_edge[B].append(A)
d = deque()
can_arrive = set()
d.append(N)
can_arrive.add(N)
while d:
	x = d.popleft()
	for y in rev_edge[x]:
		if not y in can_arrive:
			d.append(y)
			can_arrive.add(y)
for i in range(N):
	update = False
	for j in range(M):
		(A, B, cost) = edge[j]
		if dis[A] != INF and dis[B] > dis[A] + cost:
			dis[B] = dis[A] + cost
			if B in can_arrive:
				update = True
ans = dis[N]
if update:
	print(-1)
else:
	print(max(0, -ans))


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))


INF = 1000000000000.0
(n, m, p) = map(int, input().split())
grafo = []
for x in range(m):
	(a, b, c) = map(int, input().split())
	grafo.append((a - 1, b - 1, c - p))

def bellman_ford(v):
	distancia = [float('inf')] * n
	distancia[v] = 0
	for i in range(2 * n):
		for (a, b, c) in grafo:
			if distancia[b] > distancia[a] - c:
				distancia[b] = distancia[a] - c
				if i == n - 1:
					distancia[b] = -float('inf')
	return distancia
distancia = bellman_ford(0)
if distancia[-1] == -float('inf'):
	print(-1)
elif distancia[-1] > 0:
	print(0)
else:
	print(-1 * distancia[-1])


from collections import deque

def use_path(n, start, es):
	q = deque()
	chk = [False] * n
	q.append(start)
	chk[start] = True
	used = {start}
	while len(q) > 0:
		node = q.popleft()
		for nex in es[node]:
			if not chk[nex]:
				chk[nex] = True
				q.append(nex)
				used.add(nex)
	return used

def belman(s, g, n, es):
	d = [10 ** 10] * n
	d[s] = 0
	fin = False
	cnt = 0
	while True:
		update = False
		for (p, q, r) in es:
			if d[p] != 10 ** 10 and d[q] > d[p] + r:
				d[q] = d[p] + r
				update = True
		cnt += 1
		if not update:
			fin = True
			break
		if cnt > n + 1:
			break
	if fin:
		return max(0, -d[g])
	else:
		return -1
(n, m, p) = list(map(int, input().split()))
l = [[] for i in range(n)]
r = [[] for i in range(n)]
edges = []
for i in range(m):
	(a, b, c) = list(map(int, input().split()))
	a -= 1
	b -= 1
	l[a].append(b)
	r[b].append(a)
	edges.append((a, b, -c + p))
use_nodes = use_path(n, 0, l) & use_path(n, n - 1, r)
es = [(a, b, c) for (a, b, c) in edges if a in use_nodes and b in use_nodes]
print(belman(0, n - 1, n, es))


(N, M, P) = map(int, input().split())
INF = 10 ** 18
edges = []
E = [[] for _ in range(N)]
R = [[] for _ in range(N)]
for _ in range(M):
	(fr, to, c) = map(int, input().split())
	fr -= 1
	to -= 1
	edges.append((fr, to, -(c - P)))
	E[fr].append(to)
	R[to].append(fr)

def existsPath(s, edges):
	visited = [False] * N
	visited[s] = True
	st = [s]
	while st:
		now = st.pop()
		for to in edges[now]:
			if visited[to]:
				continue
			st.append(to)
			visited[to] = True
	return visited
canGoFrom1 = existsPath(0, E)
canGoFromN = existsPath(N - 1, R)
minDist = [INF] * N
minDist[0] = 0
for i in range(N):
	for (fr, to, c) in edges:
		d = minDist[fr] + c
		if minDist[to] > d:
			if i == N - 1 and canGoFrom1[fr] and canGoFromN[to]:
				print('-1')
				exit()
			minDist[to] = d
print(max(0, -minDist[N - 1]))


(n, m, p) = map(int, input().split())
el = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	el.append((a - 1, b - 1, c - p))
cost = [-float('inf') for _ in range(n)]
cost[0] = 0
for i in range(2 * n):
	for j in range(m):
		e = el[j]
		if cost[e[1]] < cost[e[0]] + e[2]:
			cost[e[1]] = cost[e[0]] + e[2]
			if i >= n:
				cost[e[1]] = float('inf')
	if i == n - 1:
		ans = cost[-1]
if ans != cost[-1]:
	print(-1)
else:
	print(max(ans, 0))


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))
main()


from collections import defaultdict
from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix
(N, M, P) = list(map(int, input().split()))
d = defaultdict(lambda : P)
for _ in range(M):
	(a, b, c) = list(map(int, input().split()))
	d[a - 1, b - 1] = min(d[a - 1, b - 1], P - c)
M = len(d)
(frm, to, length) = ([], [], [])
for ((a, b), c) in list(d.items()):
	frm.append(a)
	to.append(b)
	length.append(c)
connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
(_, labels) = connected_components(connect_check, connection='strong')
label_num = labels[0]
(frm_c, to_c, length_c) = ([], [], [])
for i in range(M):
	if labels[frm[i]] == labels[to[i]] == label_num:
		frm_c.append(frm[i])
		to_c.append(to[i])
		length_c.append(length[i])
matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))
try:
	ans = -int(bellman_ford(matr, indices=0)[N - 1])
	print(max(0, ans))
except NegativeCycleError:
	print(-1)


(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]))


def resolve():

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


import sys
(N, M, P) = map(int, input().split())
Edgeinv = [[] for _ in range(N + 1)]
Edge = [[] for _ in range(N + 1)]
inf = 2 * 10 ** 10
Edgenum = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
for (a, b, c) in Edgenum:
	Edgeinv[b].append(a)
	Edge[a].append(b)
used = set([N])
stack = [N]
while stack:
	vn = stack.pop()
	for vf in Edgeinv[vn]:
		if vf not in used:
			used.add(vf)
			stack.append(vf)
used2 = set([1])
stack = [1]
while stack:
	vn = stack.pop()
	for vf in Edge[vn]:
		if vf not in used2:
			used2.add(vf)
			stack.append(vf)
Edgenum = [(a, b, c) for (a, b, c) in Edgenum if a in used and b in used]
used &= used2
dp = [-inf] * (N + 1)
dp[1] = 0
for i in range(N - 1):
	dp2 = dp[:]
	for (a, b, c) in Edgenum:
		dp2[b] = max(dp2[b], dp[a] + c - P)
	dp = dp2[:]
Dp = dp[:]
for i in range(N):
	dp2 = dp[:]
	for (a, b, c) in Edgenum:
		dp2[b] = max(dp2[b], dp[a] + c - P)
	dp = dp2[:]
if any((Dp[i] < dp2[i] for i in used)):
	print(-1)
else:
	print(max(0, Dp[N]))


from collections import defaultdict as dd
import sys
sys.setrecursionlimit(6000)
(N, M, P) = map(int, input().split())
edges = []
revedgedict = dd(dict)
for _ in range(M):
	(f, t, c) = map(int, input().split())
	edges.append((f - 1, t - 1, -(c - P)))
	revedgedict[t - 1][f - 1] = 1
visited = [False] * N

def dfs(f):
	visited[f] = True
	for t in revedgedict[f].keys():
		if not visited[t]:
			dfs(t)
dfs(N - 1)
INF = float('inf')
d = [float('inf')] * N
d[0] = 0
for i in range(N):
	updated = False
	for (f, t, c) in edges:
		if d[f] != INF and visited[t] and (d[t] > d[f] + c):
			d[t] = d[f] + c
			updated = True
	if not updated:
		break
else:
	print(-1)
	exit()
print(max(-d[-1], 0))


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)]
	edges = []
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		E[a].append(b)
		R[b].append(a)
		edges.append((a, b, p - c))
	state = [0] * n

	def dfs(v):
		if state[v] & 1:
			return
		state[v] += 1
		for nv in E[v]:
			dfs(nv)
	dfs(0)

	def rdfs(v):
		if state[v] & 2:
			return
		state[v] += 2
		for nv in R[v]:
			rdfs(nv)
	rdfs(n - 1)
	dist = [INF] * n
	dist[0] = 0
	for k in range(n):
		for (a, b, w) in edges:
			if state[a] != 3 or state[b] != 3:
				continue
			if dist[b] > dist[a] + w:
				dist[b] = dist[a] + w
				if k == n - 1:
					print(-1)
					return
	print(max(-dist[-1], 0))
resolve()


(n, m, p) = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append((b, p - c))
INF = 10 ** 18
dist = [INF] * n
dist[0] = 0
for i in range(2 * n):
	for (v, e) in enumerate(G):
		if dist[v] == INF:
			continue
		for (t, cost) in e:
			if dist[v] + cost < dist[t]:
				dist[t] = dist[v] + cost
				if i >= n - 1 and t == n - 1:
					print(-1)
					exit()
print(max(0, -dist[-1]))


import sys
(n, m, p) = map(int, input().split())
E = [[] for _ in range(n)]
inf = 10 ** 12
for _ in range(m):
	(a, b, c) = map(int, input().split())
	E[a - 1].append([b - 1, p - c])
D = [inf for _ in range(n)]
D[0] = 0
for _ in range(n):
	for ve in range(n):
		for ed in E[ve]:
			D[ed[0]] = min(D[ed[0]], D[ve] + ed[1])
for _ in range(n + 10):
	for ve in range(n):
		for ed in E[ve]:
			if D[ed[0]] > D[ve] + ed[1] and D[ed[0]] < inf // 10:
				D[ed[0]] = -inf
if D[n - 1] > -inf // 10:
	print(max(0, -D[n - 1]))
else:
	print(-1)


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')


(n, m, r) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in [0] * m]
g = [[] for _ in [0] * n]
[g[a - 1].append([b - 1, c]) for (a, b, c) in abc]
g2 = [[] for _ in [0] * n]
[g2[b - 1].append([a - 1, c]) for (a, b, c) in abc]

def remove_edge(graph, start):
	q = [start]
	memo = [True for _ in range(n)]
	memo[start] = False
	while q:
		qq = q.pop()
		for (i, j) in graph[qq]:
			if memo[i]:
				q.append(i)
				memo[i] = False
	return {i for (i, j) in enumerate(memo) if j == True}
rmv = remove_edge(g, 0) | remove_edge(g2, n - 1)
for i in rmv:
	g[i] = []
for i in range(n):
	for j in g[i]:
		if j[0] in rmv:
			g[i].remove(j)
dist = [-10 ** 15 for _ in [0] * n]
dist[0] = 0
for k in range(n):
	for p in range(n):
		for (i, j) in g[p]:
			dist[i] = max(dist[i], dist[p] + j - r)
	if k == n - 2:
		d1 = [t for t in dist]
	if k == n - 1:
		d2 = [t for t in dist]
if d1 == d2:
	print(max(d1[-1], 0))
else:
	print(-1)


(n, m, p) = map(int, input().split())
data = [list(map(int, input().split())) for i in range(m)]
inf = float('inf')
dist = [-inf] * (n + 1)
dist[1] = 0
for i in range(n - 1):
	for (a, b, c) in data:
		if dist[a] != -inf:
			dist[b] = max(dist[b], dist[a] + c - p)
lst = []
for (a, b, c) in data:
	if dist[b] < dist[a] + c - p:
		lst.append(b)
tag = [[] for i in range(n + 1)]
for (a, b, c) in data:
	tag[a].append(b)
flag = [0] * (n + 1)
for u in lst:
	if flag[u] == 0:
		flag[u] = 1
		que = [u]
		while que:
			h = que.pop()
			for v in tag[h]:
				if flag[v] == 0:
					que.append(v)
					flag[v] = 1
if flag[n] == 1:
	print(-1)
else:
	print(max(0, dist[n]))


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
(N, M, P) = map(int, input().split())
es = []
to = defaultdict(list)
rto = defaultdict(list)
rf = [False] * N
rt = [False] * N
for i in range(M):
	(a, b, c) = map(int, input().split())
	es += [(a - 1, b - 1, -c + P)]
	to[a - 1] += [b - 1]
	rto[b - 1] += [a - 1]

def dfs(v):
	if rf[v]:
		return
	rf[v] = True
	for u in to[v]:
		dfs(u)

def rdfs(v):
	if rt[v]:
		return
	rt[v] = True
	for u in rto[v]:
		rdfs(u)
dfs(0)
rdfs(N - 1)
ok = [False] * N
for i in range(N):
	ok[i] = rf[i] & rt[i]
dist = [float('inf')] * N
dist[0] = 0
upd = True
cnt = 0
while upd:
	upd = False
	for j in range(M):
		(f, t, c) = es[j]
		if not ok[f] or not ok[t]:
			continue
		if dist[t] > dist[f] + c:
			upd = True
			dist[t] = dist[f] + c
	cnt += 1
	if cnt > N:
		print(-1)
		break
else:
	print(max(0, -dist[N - 1]))


(N, M, P) = map(int, input().split())
edge_dic = {}
for _ in range(M):
	(A, B, C) = map(int, input().split())
	if not A - 1 in edge_dic:
		edge_dic[A - 1] = [[B - 1, C - P]]
	else:
		edge_dic[A - 1].append([B - 1, C - P])
INF = 10 ** 10
ans_array = [-INF] * N
can_visit = [0] * N
ans_array[0] = 0
can_visit[0] = 1
last_ans_change = -1
for i in range(N * 2):
	change_flag = 0
	for (key, value) in edge_dic.items():
		if can_visit[key] == 0:
			continue
		for v in value:
			(goal, cost) = v
			if ans_array[goal] < ans_array[key] + cost:
				ans_array[goal] = ans_array[key] + cost
				if i >= N:
					ans_array[goal] = INF
				can_visit[goal] = 1
				change_flag = 1
				if goal == N - 1:
					last_ans_change = i
					if i >= N:
						print(-1)
						exit()
	if change_flag == 0:
		break
ans = max(0, ans_array[N - 1])
print(ans)


(N, M, P) = list(map(int, input().split()))
e_list = []
for i in range(M):
	(A, B, C) = list(map(int, input().split()))
	(A, B) = (A - 1, B - 1)
	e_list.append((A, B, P - C))
vi = 0
min_dis_list = [10 ** 27 for i in range(N)]
min_dis_list[vi] = 0
prev_list = [-1 for i in range(N)]
for i in range(N - 1):
	for e in e_list:
		(u, v, d) = e
		if min_dis_list[v] > min_dis_list[u] + d:
			min_dis_list[v] = min_dis_list[u] + d
			prev_list[v] = u
neg_loop_flag = [False for i in range(N)]
for i in range(N):
	for e in e_list:
		(u, v, d) = e
		if min_dis_list[u] < 10 ** 26:
			if min_dis_list[u] + d < min_dis_list[v]:
				neg_loop_flag[v] = True
				min_dis_list[v] = min_dis_list[u] + d
			if neg_loop_flag[u]:
				neg_loop_flag[v] = True
if neg_loop_flag[N - 1]:
	print(-1)
else:
	print(max(0, -min_dis_list[N - 1]))


import sys
input = sys.stdin.readline
(N, M, P) = map(int, input().split())
INF = 10 ** 9
G = []
for _ in range(M):
	(A, B, C) = map(int, input().split())
	G += [[A - 1, B - 1, P - C]]
check = [False] * N
d = [INF] * N

def shortest_path(s):
	s -= 1
	d[s] = 0
	j = 0
	while j < N - 1:
		for i in range(M):
			e = G[i]
			if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
		j += 1
	j = 0
	while j < N:
		for i in range(M):
			e = G[i]
			if d[e[0]] == INF:
				continue
			if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				check[e[1]] = True
			if check[e[0]]:
				check[e[1]] = True
		j += 1
shortest_path(1)
if check[N - 1]:
	print(-1)
else:
	ans = d[N - 1]
	print(max(0, -ans))


(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))


def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [-inf for i in range(num_v)]
	dist[source - 1] = 0
	buf = 0
	for i in range(num_v * 2):
		for edge in edges:
			if dist[edge[1] - 1] < dist[edge[0] - 1] + edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
				if i >= num_v:
					dist[edge[1] - 1] = inf
		if i == num_v - 1:
			buf = dist[-1]
	if dist[-1] != buf or dist[-1] == -inf:
		return -1
	return max(dist[-1], 0)
import sys

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
mod = 10 ** 9 + 7
inf = float('inf')
ans = []
(N, M, P) = LI()
cou = int(0)
maxC = 10000
d = [[float('inf') for i in range(N)] for i in range(N)]
V = [] * M
for i in range(M):
	(a, b, c) = list(map(int, input().split()))
	V.append((a, b, c - P))
print(BellmanFord(V, N, 1))


import sys

def main():
	input = sys.stdin.readline
	(N, M, P) = map(int, input().split())
	E = []
	G = [[] for _ in range(N)]
	H = [[] for _ in range(N)]
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		E.append((a, b, c - P))
		G[b].append(a)
		H[a].append(b)
	R1 = [False] * N
	R1[0] = True
	stk = [0]
	while stk:
		v = stk.pop()
		for to in H[v]:
			if R1[to]:
				continue
			R1[to] = True
			stk.append(to)
	R2 = [False] * N
	R2[N - 1] = True
	stk = [N - 1]
	while stk:
		v = stk.pop()
		for to in G[v]:
			if R2[to]:
				continue
			R2[to] = True
			stk.append(to)
	INF = 10 ** 10
	d = [-INF] * N
	d[0] = 0
	for i in range(N):
		for (a, b, c) in E:
			if R1[a] == False:
				continue
			if R2[b] == False:
				continue
			if d[a] == -INF:
				continue
			if d[b] < d[a] + c:
				d[b] = d[a] + c
				if i == N - 1:
					print(-1)
					return
	print(max(0, d[N - 1]))
main()


f = lambda : map(int, input().split())
(V, E, P) = f()
G = []
for _ in range(E):
	(s, t, d) = f()
	G.append((s, t, -(d - P)))
INF = float('inf')
res = [INF] * (V + 1)
res[1] = 0

def Bellman_Ford():
	for (s, t, d) in G:
		res[t] = min(res[t], res[s] + d)
negative_flg = False
r = INF
for _ in range(V):
	tmp = res[:]
	Bellman_Ford()
	r = min(res[-1], r)
	if tmp == res:
		break
else:
	r0 = res[-1]
	for _ in range(V):
		tmp = res[:]
		for (s, t, d) in G:
			if res[t] > res[s] + d:
				res[t] = -INF
	if r0 != res[-1]:
		negative_flg = True
if negative_flg:
	print(-1)
else:
	print(max(-r, 0))


import sys
sys.setrecursionlimit(1000000000)
ii = lambda : int(input())
mis = lambda : list(map(int, input().split()))
lmis = lambda : list(mis())

def main():
	(N, M, P) = mis()
	to = [[] for _ in range(N)]
	ot = [[] for _ in range(N)]
	edges = []
	for i in range(M):
		(a, b, c) = mis()
		a -= 1
		b -= 1
		c = -(c - P)
		to[a].append(b)
		ot[b].append(a)
		edges.append((a, b, c))
	reachableFrom0 = set()
	reachableToN = set()
	reachableFrom0.add(0)
	nodes = [0]
	while nodes:
		node = nodes.pop()
		for i in to[node]:
			if i not in reachableFrom0:
				nodes.append(i)
				reachableFrom0.add(i)
	reachableToN.add(N - 1)
	nodes = [N - 1]
	while nodes:
		node = nodes.pop()
		for i in ot[node]:
			if i not in reachableToN:
				nodes.append(i)
				reachableToN.add(i)
	ok = reachableFrom0 & reachableToN
	edges = tuple(((a, b, c) for (a, b, c) in edges if a in ok and b in ok))
	V = [float('inf')] * N
	V[0] = 0

	def bf(n):
		for _ in range(n):
			upd = False
			for (a, b, c) in edges:
				if V[b] > V[a] + c:
					V[b] = V[a] + c
					upd = True
			if not upd:
				return False
		return True
	bf(N)
	if not bf(1):
		print(max(-V[-1], 0))
	else:
		print(-1)
main()


import sys
from collections import deque
read = sys.stdin.read
INF = 1 << 60

def main():
	(N, M, P, *ABC) = list(map(int, read().split()))
	G = [[] for _ in range(N)]
	G_rev = [[] for _ in range(N)]
	edge = []
	for (a, b, c) in zip(*[iter(ABC)] * 3):
		a -= 1
		b -= 1
		c = P - c
		G[a].append(b)
		G_rev[b].append(a)
		edge.append((a, b, c))
	reachable_1 = [False] * N
	reachable_N = [False] * N
	reachable_1[0] = True
	reachable_N[N - 1] = True
	queue = deque([0])
	while queue:
		v = queue.popleft()
		for nv in G[v]:
			if not reachable_1[nv]:
				reachable_1[nv] = True
				queue.append(nv)
	queue = deque([N - 1])
	while queue:
		v = queue.popleft()
		for nv in G_rev[v]:
			if not reachable_N[nv]:
				reachable_N[nv] = True
				queue.append(nv)
	ok = [reachable_1[i] and reachable_N[i] for i in range(N)]
	dist = [INF] * N
	dist[0] = 0
	for i in range(N):
		for (a, b, c) in edge:
			if not ok[a] or not ok[b]:
				continue
			if dist[b] > dist[a] + c:
				if i < N - 1:
					dist[b] = dist[a] + c
				else:
					print(-1)
					return
	score = -dist[N - 1]
	print(max(score, 0))
	return

def __starting_point():
	main()
__starting_point()


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

def BF(edges, num_v, source):
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source - 1] = 0
	neg = [False for _ in range(num_v)]
	for i in range(num_v - 1):
		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]
	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]
				neg[edge[1] - 1] = True
			if neg[edge[0] - 1] == True:
				neg[edge[1] - 1] = True
	return (dist, neg)
(dis, neg) = BF(abc, n, 1)
print(-1 if neg[-1] else max(0, -dis[-1]))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, M, P) = map(int, input().split())
ABC = [[int(x) for x in input().split()] for _ in range(M)]
INF = 10 ** 18
dist = [INF] * (N + 1)
dist[1] = 0
loop = False
for i in range(2 * N + 100):
	for (a, b, c) in ABC:
		x = dist[a] + P - c
		if dist[b] > x:
			dist[b] = x
			if b == N and i > N:
				loop = True
if loop:
	answer = -1
else:
	answer = -dist[N]
	if answer < 0:
		answer = 0
print(answer)


import sys
input = sys.stdin.readline
(N, M, P) = map(int, input().split())
edges = [None] * M
for i in range(M):
	(A, B, C) = map(int, input().split())
	edges[i] = (A, B, P - C)
dist = [float('inf')] * (N + 1)
dist[1] = 0
for i in range(N - 1):
	for (u, v, weight) in edges:
		if dist[v] > dist[u] + weight:
			dist[v] = dist[u] + weight
negative = [False] * (N + 1)
for i in range(N):
	for (u, v, weight) in edges:
		if negative[u]:
			negative[v] = True
		if dist[v] > dist[u] + weight:
			dist[v] = dist[u] + weight
			negative[v] = True
print(max(-dist[N], 0) if not negative[N] else -1)


import sys
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

def BFord(n, es):
	v_cost = [INF] * n
	v_cost[0] = 0
	for v in range(n * 2):
		for e in es:
			frm = e[0]
			to = e[1]
			if v_cost[to] > v_cost[frm] + e[2]:
				v_cost[to] = v_cost[frm] + e[2]
				if v >= n:
					v_cost[to] = -INF
		if v == n - 1:
			prev = v_cost[:]
	v_cost = [-INF if prev[idx] != v_cost[idx] else v_cost[idx] for idx in range(n)]
	return v_cost

def main():
	(n, m, p) = map(int, input().split())
	es = []
	for _ in range(m):
		e = list(map(int, input().split()))
		es.append([e[0] - 1, e[1] - 1, -e[2] + p])
	v_cost = BFord(n, es)
	if v_cost[-1] == -INF:
		return -1
	return max(0, -v_cost[-1])
print(main())


from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix
from collections import defaultdict
(n, m, p) = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]
INF = 10 ** 9
fwd = [[] for _ in range(n + 1)]
rev = [[] for _ in range(n + 1)]
for (a, b, c) in abc:
	fwd[a].append(b)
	rev[b].append(a)

def dfs(s, adj):
	stack = [s]
	arrived = [False] * (n + 1)
	arrived[s] = True
	while stack:
		u = stack.pop()
		for v in adj[u]:
			if not arrived[v]:
				arrived[v] = True
				stack.append(v)
	return arrived
can_go_fwd = dfs(1, fwd)
can_go_rev = dfs(n, rev)
data = defaultdict(lambda : INF)
for (a, b, c) in abc:
	if can_go_fwd[a] and can_go_rev[b]:
		data[a, b] = min(data[a, b], p - c)
row = []
col = []
cost = []
for ((a, b), c) in list(data.items()):
	row.append(a)
	col.append(b)
	cost.append(c)
g = csr_matrix((cost, (row, col)), shape=(n + 1, n + 1))
try:
	dist = bellman_ford(g, indices=[1]).astype(int)
	ans = max(0, -dist[0][n])
	print(ans)
except NegativeCycleError:
	print(-1)


(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)


(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)


import sys
sys.setrecursionlimit(10000000)
f_inf = sys.maxsize
(N, M, P) = map(int, input().split())
ABC_d = {}
for m in range(M):
	(A, B, C) = map(int, input().split())
	if A in ABC_d:
		ABC_d[A].append([B, C - P])
	else:
		ABC_d[A] = [[B, C - P]]
cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
	global cost
	if not pos in ABC_d:
		return
	if cnt > N:
		cost[pos - 1] = f_inf
	for (B, C) in ABC_d[pos]:
		if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
			pass
		elif cost[pos - 1] == f_inf:
			cost[B - 1] = f_inf
			solve(B, cnt + 1)
		elif cost[B - 1] < cost[pos - 1] + C:
			cost[B - 1] = cost[pos - 1] + C
			solve(B, cnt + 1)
solve(1, 1)
if cost[-1] == sys.maxsize:
	print(-1)
else:
	print(max(0, int(cost[-1])))


(n, m, p) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
	A[i][2] = -(A[i][2] - p)
S = [10 ** 10 for i in range(n + 1)]
S[1] = 0
for i in range(m):
	if A[i][0] == 1:
		S[A[i][1]] = A[i][2]
for j in range(n - 1):
	for i in range(m):
		S[A[i][1]] = min(S[A[i][1]], S[A[i][0]] + A[i][2])
ans0 = -S[n]
for j in range(n - 1):
	for i in range(m):
		S[A[i][1]] = min(S[A[i][1]], S[A[i][0]] + A[i][2])
ans1 = -S[n]
if ans0 != ans1:
	print(-1)
else:
	print(max(0, ans0))


import sys
input = sys.stdin.readline

def BellmanFord(Edges, num_v, start, goal):
	inf = float('inf')
	Dist = [inf] * num_v
	Dist[start] = 0
	for _ in range(num_v):
		for (fr, to, cost) in Edges:
			if Dist[fr] != inf and Dist[to] > Dist[fr] + cost:
				Dist[to] = Dist[fr] + cost
	d = Dist[goal]
	for _ in range(num_v):
		for (fr, to, cost) in Edges:
			if Dist[fr] != inf and Dist[to] > Dist[fr] + cost:
				Dist[to] = -inf
	if d != Dist[goal]:
		return -inf
	return d
(n, m, p) = map(int, input().split())
Edges = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	Edges.append((a, b, -(c - p)))
d = BellmanFord(Edges, n, 0, n - 1)
print(-1 if d == -float('inf') else max(0, -d))


(N, M, P) = map(int, input().split())
dist = [0] + [float('inf')] * (N - 1)
a = []
b = []
c = []
for i in range(M):
	(i, j, k) = map(int, input().split())
	a.append(i)
	b.append(j)
	c.append(-1 * (k - P))
INF = float('inf')
for i in range(N - 1):
	for j in range(M):
		if dist[a[j] - 1] == INF:
			continue
		if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
			dist[b[j] - 1] = dist[a[j] - 1] + c[j]
ans = dist[N - 1]
negative = [False] * N
for i in range(N):
	for j in range(M):
		if dist[a[j] - 1] == INF:
			continue
		if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
			dist[b[j] - 1] = dist[a[j] - 1] + c[j]
			negative[b[j] - 1] = True
		if negative[a[j] - 1] == True:
			negative[b[j] - 1] = True
if negative[N - 1]:
	print(-1)
else:
	print(max(-1 * ans, 0))


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
		elif earn[n[0]] < n[1] + earn[now] - P:
			if isConnected(n[0]) == True:
				print(-1)
				exit(0)
dfs(1)
print(max(earn[N], 0))


import sys
sys.setrecursionlimit(10000)
(N, M, P) = map(int, input().split())
ways = [[] for _ in range(N)]
Rways = [[] for _ in range(N)]
for i in range(M):
	(A, B, C) = map(int, input().split())
	ways[A - 1].append([B - 1, C - P])
	Rways[B - 1].append(A - 1)
visited = [-float('inf')] * N
visited[0] = 0
blacklist = [True] * N
blacklist[-1] = False

def b_update(nord):
	global blacklist
	for to in Rways[nord]:
		if blacklist[to] == True:
			blacklist[to] = False
			b_update(to)
b_update(N - 1)
for c in range(N):
	flag = False
	for i in range(N):
		debit = visited[i]
		if debit == -float('inf'):
			continue
		for (to, cost) in ways[i]:
			if visited[to] < debit + cost and (not blacklist[to]):
				visited[to] = debit + cost
				flag = True
	if not flag:
		break
	if c == N - 1:
		print(-1)
		exit()
ans = visited[-1]
if ans == -float('inf'):
	print(-1)
else:
	print(max(ans, 0))


def is_reachable(edges, start, end):
	g = {}
	for (f, t, w) in edges:
		if f in g:
			g[f].append(t)
		else:
			g[f] = [t]
	visiting = [start]
	visited = {}
	while visiting:
		v = visiting.pop()
		if v in visited:
			continue
		if v == end:
			return True
		visited[v] = True
		for v2 in g.get(v, ()):
			if v2 in visited or v2 in visiting:
				continue
			visiting.append(v2)
	return False
(N, M, P) = map(int, input().split())
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a, b, c))
neg_inf = float('-Inf')
no_answer = False
start = 1
end = N
distance = {}
for i in range(1, N + 1):
	distance[i] = neg_inf
distance[start] = 0
for i in range(N - 1):
	for (f, t, w) in edges:
		if distance[f] + w - P > distance[t]:
			distance[t] = distance[f] + w - P
for (f, t, w) in edges:
	if distance[f] + w - P > distance[t] and is_reachable(edges, t, end):
		no_answer = True
		break
if no_answer:
	print(-1)
else:
	print(max(0, distance[end]))


from collections import deque

def dfs(edge, s):
	used = {s}
	que = deque([s])
	while que:
		v = que.pop()
		for u in edge[v]:
			if u in used:
				continue
			used.add(u)
			que.append(u)
	return used

def bellmanFord(edges):
	coins = [float('inf')] * N
	coins[0] = 0
	for _ in range(N):
		f = True
		for (u, v, c) in edges:
			if coins[u] + c < coins[v]:
				coins[v] = coins[u] + c
				f = False
		if f:
			return max(0, -coins[-1])
	return -1
(N, M, P) = map(int, input().split())
A = [[] for _ in range(N)]
A_rev = [[] for _ in range(N)]
E = [tuple()] * M
for i in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c = P - c
	A[a].append(b)
	A_rev[b].append(a)
	E[i] = (a, b, c)
U = dfs(A, 0) & dfs(A_rev, N - 1)
F = [(a, b, c) for (a, b, c) in E if a in U and b in U]
print(bellmanFord(F))


import numpy as np
from collections import defaultdict
from scipy.sparse.csgraph import bellman_ford, connected_components
from scipy.sparse import csr_matrix
(N, M, P) = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]
ABC_max = defaultdict(int)
for (a, b, c) in ABC:
	ABC_max[a, b] = max(ABC_max[a, b], c)
ABC = np.array([[a, b, c] for ((a, b), c) in ABC_max.items()], np.int64)
A = ABC[:, 0] - 1
B = ABC[:, 1] - 1
C = ABC[:, 2] - P
L = csr_matrix((C, (A, B)), (N, N))
L[N - 1, 0] = 1
(_, label) = connected_components(L, connection='strong')
label = np.arange(N)[label == label[0]]
ABC = ABC[np.isin(ABC[:, :2], label + 1).all(axis=1)]
A = ABC[:, 0] - 1
B = ABC[:, 1] - 1
C = ABC[:, 2] - P
L = csr_matrix((-C, (A, B)), (N, N))
try:
	dist = bellman_ford(L, indices=0).astype(np.int64)
	print(max(0, -dist[-1]))
except:
	print(-1)


(n, m, p) = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
	lst[i][2] = -(lst[i][2] - p)
d = [10 ** 100] * (n + 1)
d[1] = 0
rep = 0
while True:
	update = False
	for edge in lst:
		(a, b, c) = edge
		if d[a] != 10 ** 100 and d[b] > d[a] + c:
			if rep >= n:
				d[b] = -10 ** 100
			else:
				d[b] = d[a] + c
			update = True
	if not update:
		break
	rep += 1
	if rep > 2 * n:
		break
if d[n] <= -10 ** 100:
	print(-1)
elif -d[n] < 0:
	print(0)
else:
	print(-d[n])


def bellman_ford(s):
	d = [inf] * n
	d[s] = 0
	ref = inf
	for cnt in range(n * 2):
		for (s, t, w) in g:
			if d[s] != inf and d[t] > d[s] + w:
				d[t] = d[s] + w
		if cnt == n - 1:
			ref = d[n - 1]
	if ref == d[n - 1]:
		return max(0, -ref)
	else:
		return -1
inf = float('inf')
(n, m, p) = map(int, input().split())
g = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	g.append((a, b, -(c - p)))
ans = bellman_ford(0)
print(ans)


(N, M, P) = map(int, input().split())
es = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	es.append((a - 1, b - 1, c))
INF = float('inf')
d = [INF for _ in range(N)]
d[0] = 0

def solve(start, f):
	for i in range(N):
		for (a, b, c) in es:
			if d[a] != INF and d[a] + -c + P < d[b]:
				if f == 0:
					d[b] = d[a] + -c + P
				else:
					d[b] = -INF
	return d[-1]
first = solve(0, 0)
second = solve(0, 1)
if first != second:
	print(-1)
else:
	print(max(-first, 0))


class Edge:

	def __init__(self, starting_point, arrival_point, cost):
		self.starting_point = starting_point
		self.arrival_point = arrival_point
		self.cost = cost

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


(n, m, p) = map(int, input().split())
edge = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	edge.append((a, b, p - c))
INF = float('inf')

def bellmanford(s, n):
	d = [INF for i in range(n + 1)]
	d[s] = 0
	for i in range(n - 1):
		for (a, b, c) in edge:
			if d[b] > d[a] + c:
				d[b] = d[a] + c
	for i in range(n - 1):
		for (a, b, c) in edge:
			if d[b] > d[a] + c:
				d[b] = -INF
	return d
d = bellmanford(1, n)
if d[n] == -INF:
	print(-1)
elif d[n] >= 0:
	print(0)
else:
	print(-d[n])


import sys
input = sys.stdin.readline

def main():
	(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, P - C])
	inf = 10000 * 10 ** 5
	dist = [inf for _ in range(N)]
	dist[0] = 0
	for i in range(N - 1):
		for edge in edges:
			if dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
	ans = -1 * dist[N - 1]
	for i in range(N - 1):
		for edge in edges:
			if dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
	ans2 = -1 * dist[N - 1]
	if ans2 <= ans:
		print(max(0, ans))
	else:
		print(-1)
main()


import sys
input = sys.stdin.readline
(n, m, p) = map(int, input().split())
edges = []
forward_edges = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	edges.append((a, b, p - c))
	forward_edges[a].append(b)
can_reach = [0] * n
stack = [0]
while stack:
	v = stack.pop()
	if can_reach[v]:
		continue
	can_reach[v] = 1
	for v2 in forward_edges[v]:
		if can_reach[v2]:
			continue
		stack.append(v2)
INF = 10 ** 10
dist = [INF] * n
dist[0] = 0
for i in range(n):
	for (v, v2, c) in edges:
		if dist[v2] <= dist[v] + c:
			continue
		dist[v2] = dist[v] + c
negative = [0] * n
for i in range(n):
	for (v, v2, c) in edges:
		if dist[v2] <= dist[v] + c:
			continue
		if not can_reach[v2]:
			continue
		dist[v2] = -INF
		negative[v2] = 1
if negative[-1]:
	print(-1)
else:
	print(max(0, -dist[-1]))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)

def find_negative_loop(n, e):
	d = n * [10 ** 20]
	d[0] = 0
	for h in range(n):
		for (i, j, k) in e:
			if d[j] > d[i] + k:
				d[j] = d[i] + k
				if h == n - 1:
					return -1
	return max(-d[n - 1], 0)
from collections import deque

def find_loop(n, e, flag):
	x = [0] * n
	d = deque()
	t = []
	c = 0
	for i in range(n):
		for j in e[i]:
			x[j] += 1
	for i in range(n):
		if x[i] == 0:
			d.append(i)
			t.append(i)
			c += 1
	while d:
		i = d.popleft()
		for j in e[i]:
			x[j] -= 1
			if x[j] == 0:
				d.append(j)
				t.append(j)
				c += 1
	if flag == 0:
		return c == n
	else:
		return t
(n, m, p) = map(int, input().split())
ef = [[] for _ in range(n)]
ee = [[] for _ in range(n)]
edge = [[] for _ in range(n)]
e = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c -= p
	ef[a].append(b)
	ee[b].append(a)
	edge[a].append((b, c))
	e.append((a, b, c))
eff = [0] * n
eff[0] = 1
Q = [0]
visited = {0}
while Q:
	P = []
	for i in Q:
		for j in ef[i]:
			if j in visited:
				continue
			visited.add(j)
			eff[j] = 1
			P.append(j)
	Q = P
eef = [0] * n
eef[n - 1] = 1
Q = [n - 1]
visited = {n - 1}
while Q:
	P = []
	for i in Q:
		for j in ee[i]:
			if j in visited:
				continue
			visited.add(j)
			eef[j] = 1
			P.append(j)
	Q = P
ee = []
for (a, b, c) in e:
	if eff[a] == 1 and eef[a] == 1 and (eff[b] == 1) and (eef[b] == 1):
		ee.append((a, b, -c))
print(find_negative_loop(n, ee))


def e_coins_respawn(N, M, P, Edges, INF=float('inf')):
	edges = [(a - 1, b - 1, P - c) for (a, b, c) in Edges]
	dist = [INF] * N
	dist[0] = 0
	for _ in range(N - 1):
		for (u, v, w) in edges:
			if dist[u] == INF:
				continue
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
	ans_tmp = dist[N - 1]
	is_negative = [False] * N
	for _ in range(N):
		for (u, v, w) in edges:
			if dist[u] == INF:
				continue
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				is_negative[v] = True
			if is_negative[u]:
				is_negative[v] = True
	return -1 if is_negative[N - 1] else max(-ans_tmp, 0)
(N, M, P) = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(e_coins_respawn(N, M, P, Edges))


(n, m, p) = map(int, input().split())
graph = [[] for _ in range(n)]
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for _ in range(m):
	(f, t, c) = map(int, input().split())
	graph[f - 1].append((t - 1, p - c))
for _ in range(n):
	update = False
	for (f, e) in enumerate(graph):
		for (t, c) in e:
			if dist[f] != INF and dist[t] > dist[f] + c:
				dist[t] = dist[f] + c
				update = True
	if not update:
		break
else:
	prev = dist[-1]
	for _ in range(n):
		for (f, e) in enumerate(graph):
			for (t, c) in e:
				if dist[f] != INF and dist[t] > dist[f] + c:
					dist[t] = -INF
	if dist[-1] != prev:
		print(-1)
		exit()
print(max(0, dist[-1] * -1))


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

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

def __starting_point():
	main()
__starting_point()


(n, m, p) = map(int, input().split())
graph = [[] for _ in range(n)]
edge = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append((b, -c + p))
	edge.append((a, b, -c + p))
INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
	for (v_from, v_to, cost) in edge:
		if d[v_from] != INF and d[v_to] > d[v_from] + cost:
			d[v_to] = d[v_from] + cost
exist = True
for i in range(n):
	for (v_from, v_to, cost) in edge:
		if d[v_from] != INF and d[v_to] > d[v_from] + cost:
			d[v_to] = d[v_from] + cost
			if v_to == n - 1:
				exist = False
if not exist:
	print(-1)
else:
	print(max(0, -d[n - 1]))


import sys

def solve(N: int, M: int, P: int, A: 'List[int]', B: 'List[int]', C: 'List[int]'):
	import numpy as np
	from scipy.sparse import csr_matrix
	from scipy.sparse.csgraph import bellman_ford, NegativeCycleError

	def to_csr_matrix(X, Y, Z, shape, dtype):
		d = {}
		for (x, y, z) in zip(X, Y, Z):
			d[x, y] = max(d.get((x, y), -float('inf')), z)
		(ind, data) = list(zip(*list(d.items())))
		return csr_matrix((data, list(zip(*ind))), shape=shape, dtype=dtype)
	smat = bellman_ford(csr_matrix((C, (A, B)), shape=(N + 1, N + 1), dtype=np.int32), directed=True, unweighted=True, indices=1)
	tmat = bellman_ford(csr_matrix((C, (B, A)), shape=(N + 1, N + 1), dtype=np.int32), directed=True, unweighted=True, indices=N)
	r = set([i for (i, v) in enumerate(smat + tmat) if not np.isinf(v)])
	(A, B, C) = list(zip(*[(a, b, c) for (a, b, c) in zip(A, B, C) if b in r]))
	try:
		csr_mat = to_csr_matrix(A, B, C, (N + 1, N + 1), np.float64)
		csr_mat.data = P - csr_mat.data
		return -min(int(bellman_ford(csr_mat, directed=True, indices=1)[N]), 0)
	except NegativeCycleError:
		return -1

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	M = int(next(tokens))
	P = int(next(tokens))
	A = [int()] * M
	B = [int()] * M
	C = [int()] * M
	for i in range(M):
		A[i] = int(next(tokens))
		B[i] = int(next(tokens))
		C[i] = int(next(tokens))
	print(solve(N, M, P, A, B, C))

def __starting_point():
	main()
__starting_point()


import sys
from collections import deque
input = sys.stdin.readline

def belman(egdes, N, start, end):
	INF = int(10000000000.0)
	cost = [INF] * N
	cost[start] = 0
	fin = False
	count = 0
	while True:
		no_change = True
		for edge in egdes:
			(from_, to_, d) = edge
			tmp = cost[from_] + d
			if cost[to_] > tmp:
				no_change = False
				cost[to_] = tmp
		count += 1
		if no_change:
			fin = True
			break
		elif count > N + 1:
			break
	if fin:
		return max(0, -cost[end])
	else:
		return -1

def bfs(link, N, start):
	q = deque()
	check = [False] * N
	q.append(start)
	check[start] = True
	used = {start}
	while len(q) > 0:
		node = q.popleft()
		for next_ in link[node]:
			if not check[next_]:
				check[next_] = True
				q.append(next_)
				used.add(next_)
	return used

def main():
	(N, M, P) = map(int, input().split())
	link = [[] for i in range(N)]
	rlink = [[] for i in range(N)]
	edges = []
	for i in range(M):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		link[a].append(b)
		rlink[b].append(a)
		edges.append((a, b, -(c - P)))
	use_nodes = bfs(link, N, 0) & bfs(rlink, N, N - 1)
	use_edges = [(a, b, c) for (a, b, c) in edges if a in use_nodes and b in use_nodes]
	print(belman(use_edges, N, 0, N - 1))

def __starting_point():
	main()
__starting_point()


import numpy as np
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline
(N, M, P) = map(int, input().split())
G = {}
for i in range(M):
	(a, b, c) = map(int, input().split())
	(a, b, c) = (a - 1, b - 1, -1 * (c - P))
	if (a, b) in G and G[a, b] > c:
		G[a, b] = c
	elif (a, b) not in G:
		G[a, b] = c
(A, B, C) = ([], [], [])
for (k, v) in G.items():
	(a, b) = k
	c = v
	A.append(a)
	B.append(b)
	C.append(c)
CC = [1] * len(A)
smat = bellman_ford(csr_matrix((CC, (A, B)), shape=(N, N)), directed=True, unweighted=True, indices=0)
tmat = bellman_ford(csr_matrix((CC, (B, A)), shape=(N, N)), directed=True, unweighted=True, indices=N - 1)
r = set([i for (i, v) in enumerate(smat + tmat) if not np.isinf(v)])
(A, B, C) = zip(*[(a, b, c) for (a, b, c) in zip(A, B, C) if b in r])
try:
	csr_mat = csr_matrix((C, (A, B)), shape=(N, N))
	x = -int(bellman_ford(csr_mat, directed=True, indices=0)[N - 1])
	if x < 0:
		x = 0
except NegativeCycleError:
	x = -1
print(x)


import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford, connected_components
input = sys.stdin.readline

def main():
	(n, m, p) = list(map(int, input().split()))
	l = np.zeros((n, n))
	for i in range(m):
		(a, b, c) = list(map(int, input().split()))
		c = p - c
		if c == 0:
			c = 10 ** (-7.9)
		if l[a - 1][b - 1] == 0:
			l[a - 1][b - 1] = c
		else:
			l[a - 1][b - 1] = min(l[a - 1][b - 1], c)
	x = l[-1, 0]
	l[-1][0] = 10 ** (-7.9)
	(n, labels) = connected_components(l, connection='strong')
	l = l[labels == labels[0]][:, labels == labels[0]]
	l[-1, 0] = x
	try:
		print(max(0, int(round(bellman_ford(l, indices=0)[-1])) * -1))
	except:
		print(-1)

def __starting_point():
	main()
__starting_point()


(N, M, P) = map(int, input().split())
E = [list(map(int, input().split())) for _ in range(M)]
reachable = [False] * (N + 1)
reachable[N] = True
for v in range(N):
	for (a, b, c) in E:
		if reachable[b]:
			reachable[a] = True
A = [-float('inf')] * (N + 1)
A[1] = 0
for v in range(N):
	for (a, b, c) in E:
		t = A[a] + c - P
		if t > A[b]:
			A[b] = t
A_copy = A[:]
for v in range(N):
	for (a, b, c) in E:
		t = A[a] + c - P
		if t > A[b]:
			A[b] = t
for (a_copy, a, r) in zip(A_copy, A, reachable):
	if r and a_copy != a:
		print(-1)
		exit()
else:
	print(max(0, A[N]))


import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 10

class edge:

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

def input():
	return sys.stdin.readline().strip()

def Z():
	return int(input())

def ZZ():
	return [int(_) for _ in input().split()]

def main():
	(N, M, P) = ZZ()
	es = []
	for _ in range(M):
		(a, b, c) = ZZ()
		a -= 1
		b -= 1
		es.append(edge(a, b, -(c - P)))
	d = [INF] * N
	d[0] = 0
	for i in range(N - 1):
		for e in es:
			if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
				d[e.to] = d[e.fr] + e.cost
	n = [False] * N
	for i in range(N):
		for e in es:
			if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
				d[e.to] = d[e.fr] + e.cost
				n[e.to] = True
			if n[e.fr] == True:
				n[e.to] = True
	print(-1 if n[N - 1] else max(0, -d[N - 1]))
	return
main()


def e():
	(n, m, p) = map(int, input().split())
	edges = []
	for i in range(m):
		edges.append(tuple(map(int, input().split())))
	edges.sort(key=lambda x: x[1])
	dist = [float('inf') for i in range(n)]
	dist[0] = 0
	for i in range(n):
		for e in edges:
			if dist[e[1] - 1] > dist[e[0] - 1] - (e[2] - p):
				dist[e[1] - 1] = dist[e[0] - 1] - (e[2] - p)
	for i in range(n):
		for e in edges:
			if dist[e[1] - 1] > dist[e[0] - 1] - (e[2] - p):
				dist[e[1] - 1] = float('-inf')
	if dist[n - 1] == float('-inf'):
		print(-1)
	else:
		print(-dist[n - 1] if -dist[n - 1] >= 0 else 0)
e()


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

def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [-inf for i in range(num_v)]
	dist[source - 1] = 0
	buf = 0
	for i in range(num_v * 2):
		for edge in edges:
			if dist[edge[1] - 1] < dist[edge[0] - 1] + edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
				if i >= num_v:
					dist[edge[1] - 1] = inf
		if i == num_v - 1:
			buf = dist[-1]
	if dist[-1] != buf or dist[-1] == -inf:
		return -1
	return max(dist[-1], 0)
x = BellmanFord(A, n, 1)
print(x)


def reachable_nodeset(start, inc):
	reachable = set()
	reachable.add(start)
	nodes = [start]
	while nodes:
		n = nodes.pop()
		for i in inc[n]:
			if i not in reachable:
				nodes.append(i)
				reachable.add(i)
	return reachable

def bellmanford(num, start, goal, edges):
	cost = [float('inf')] * num
	cost[start] = 0
	for _ in range(num):
		updated = False
		for (a, b, c) in edges:
			if cost[b] > cost[a] + c:
				cost[b] = cost[a] + c
				updated = True
		if not updated:
			break
	else:
		return -1
	return max(0, -cost[goal])
(N, M, P) = map(int, input().split())
to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c = -(c - P)
	to[a].append(b)
	ot[b].append(a)
	edges.append((a, b, c))
reachableFromZero = reachable_nodeset(0, to)
reachableToN = reachable_nodeset(N - 1, ot)
ok = reachableFromZero.intersection(reachableToN)
edges = tuple(((a, b, c) for (a, b, c) in edges if a in ok and b in ok))
print(bellmanford(N, 0, N - 1, edges))


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]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

def BellmanFord(edges, v, source):
	INF = float('inf')
	dist = [INF for _ in range(v)]
	dist[source] = 0
	for i in range(2 * v + 1):
		for (now, fol, cost) in edges:
			if dist[now] != INF and dist[fol] > dist[now] + cost:
				dist[fol] = dist[now] + cost
				if i >= v:
					dist[fol] = -INF
	if dist[-1] == -INF:
		return -1
	else:
		return max(0, -dist[-1])
(n, m, p) = map(int, readline().split())
abc = [list(map(int, readline().split())) for i in range(m)]
edges = []
for (a, b, c) in abc:
	edges.append((a - 1, b - 1, p - c))
print(BellmanFord(edges, n, 0))


(N, M, P) = map(int, input().split())
v = [[] for _ in range(N)]
abc = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	v[b - 1].append((a - 1, -(c - P)))
visited = [False] * N
visited[N - 1] = True
queue = [N - 1]
while queue:
	cur = queue.pop()
	for (nex, cost) in v[cur]:
		if not visited[nex]:
			queue.append(nex)
			visited[nex] = True
		abc.append((nex, cur, cost))
dist = [float('inf')] * N
dist[0] = 0

def bellmanford():
	for i in range(N):
		for (a, b, c) in abc:
			if dist[a] + c < dist[b]:
				dist[b] = dist[a] + c
				if i == N - 1:
					return True
	return False
if bellmanford():
	print(-1)
else:
	print(max(0, -dist[N - 1]))


(N, M, P) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for _ in range(N)]
rs = [[] for _ in range(N)]
for (a, b, c) in ABC:
	(a, b) = (a - 1, b - 1)
	es[a].append((b, P - c))
	rs[b].append(a)
stack = [0]
govisit = set([0])
while stack:
	v = stack.pop()
	for (to, _) in es[v]:
		if to in govisit:
			continue
		govisit.add(to)
		stack.append(to)
stack = [N - 1]
backvisit = set([N - 1])
while stack:
	v = stack.pop()
	for to in rs[v]:
		if to in backvisit:
			continue
		backvisit.add(to)
		stack.append(to)
use = govisit & backvisit
INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
	for (fr, e) in enumerate(es):
		if fr not in use:
			continue
		for (to, c) in e:
			if to not in use:
				continue
			if dist[to] > dist[fr] + c:
				dist[to] = dist[fr] + c
				if i == N - 1:
					print(-1)
					exit()
print(max(0, -dist[-1]))


def shortest_path(s):
	dist[s] = 0
	for _ in range(n):
		for (fr, to, cost) in edge:
			if dist[fr] != inf and dist[to] > dist[fr] + cost:
				dist[to] = dist[fr] + cost

def find_negative_loops():
	for _ in range(n):
		for (fr, to, cost) in edge:
			if dist[fr] != inf and dist[to] > dist[fr] + cost:
				dist[to] = dist[fr] + cost
				negative[to] = True
			if negative[fr]:
				negative[to] = True
(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])
inf = float('inf')
dist = [inf] * n
negative = [False] * n
shortest_path(0)
find_negative_loops()
print(-1) if negative[-1] else print(max(-dist[-1], 0))


from collections import deque
(N, M, P) = map(int, input().split())
edges = [[] for _ in range(N)]
revEdges = [[] for _ in range(N)]
E = []
for _ in range(M):
	(fr, to, cost) = map(int, input().split())
	fr -= 1
	to -= 1
	edges[fr].append(to)
	revEdges[to].append(fr)
	E.append((fr, to, -(cost - P)))

def canVisit(start, edges):
	st = deque([start])
	minDist = [10 ** 18] * N
	minDist[start] = 0
	while st:
		now = st.popleft()
		d = minDist[now] + 1
		for to in edges[now]:
			if minDist[to] > d:
				minDist[to] = d
				st.append(to)
	return [True if minDist[to] < 10 ** 18 else False for to in range(N)]
canForward = canVisit(0, edges)
canBack = canVisit(N - 1, revEdges)
minDist = [10 ** 18] * N
minDist[0] = 0
for i in range(N + 1):
	for (fr, to, cost) in E:
		d = minDist[fr] + cost
		if minDist[to] > d:
			if i == N and canForward[fr] and canBack[to]:
				print(-1)
				exit()
			minDist[to] = d
print(max(0, -minDist[N - 1]))


(n, m, p) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
	A[i][2] = -(A[i][2] - p)
S = [[float('inf'), 0, 0] for i in range(n + 1)]
S[1][0] = 0
S[1][1] = 1
S[n][2] = 1
for i in range(m):
	if A[i][0] == 1:
		S[A[i][1]][0] = A[i][2]
for j in range(n - 1):
	for i in range(m):
		S[A[i][1]][0] = min(S[A[i][1]][0], S[A[i][0]][0] + A[i][2])
		S[A[i][1]][1] = max(S[A[i][1]][1], S[A[i][0]][1])
		S[A[i][0]][2] = max(S[A[i][1]][2], S[A[i][0]][2])
ANS0 = [S[i][0] for i in range(len(S))]
for j in range(1):
	for i in range(m):
		S[A[i][1]][0] = min(S[A[i][1]][0], S[A[i][0]][0] + A[i][2])
imp = 0
for i in range(len(S)):
	if S[i][1] == 1 and S[i][2] == 1:
		if ANS0[i] != S[i][0]:
			imp = 1
if imp == 1:
	print(-1)
else:
	print(max(0, -ANS0[n]))


(n, m, p) = map(int, input().split())
abcs = [list(map(int, input().split())) for _ in range(m)]
distance = [-1000000 * n] * (n + 1)
distance[1] = 0
reachable1 = set([1])
reachableN = set([n])
for _ in range(n + 1):
	for (a, b, c) in abcs:
		if distance[b] < distance[a] + c - p:
			distance[b] = distance[a] + c - p
		if a in reachable1:
			reachable1.add(b)
		if b in reachableN:
			reachableN.add(a)
for (a, b, c) in abcs:
	if distance[b] < distance[a] + c - p and a in reachable1 and (b in reachableN):
		print(-1)
		exit(0)
print(max(distance[n], 0))


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

def pin(type=int):
	return map(type, input().split())

def tupin(t=int):
	return tuple(pin(t))

def resolve():
	(N, M, P) = pin()
	edge = []
	for i in range(M):
		(a, b, c) = pin()
		edge.append((a - 1, b - 1, P - c))
	inf = float('inf')
	ans = [inf] * N
	ans[0] = 0
	for i in range(N * 2):
		for j in range(M):
			(t, f, p) = edge[j]
			ans[f] = min(ans[f], ans[t] + p)
			if ans[f] > ans[t] + p:
				ans[f] = 0 - inf
		if i == N:
			temp = ans[-1]
		if i == N * 2 - 1:
			if ans[-1] < temp:
				ans[-1] = 0 - inf
	t = 0 - ans[-1]
	if t == inf:
		s = -1
	elif t < 0:
		s = 0
	else:
		s = t
	print(s)
resolve()


import sys
input = sys.stdin.readline
(N, M, P) = map(int, input().split())
EDGE = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
	EDGE[i][2] -= P
from collections import deque
Q = deque([1])
ANS = [-float('inf')] * (N + 1)
ANS[1] = 0
for i in range(N + 1):
	for (a, b, p) in EDGE:
		if ANS[a] + p > ANS[b]:
			ANS[b] = ANS[a] + p
import copy
ANS2 = copy.deepcopy(ANS)
for i in range(N + 1):
	for (a, b, p) in EDGE:
		if ANS2[a] + p > ANS2[b]:
			ANS2[b] = ANS2[a] + p
if ANS[N] < ANS2[N]:
	print(-1)
else:
	print(max(ANS2[N], 0))


import sys

def input():
	return sys.stdin.readline()[:-1]
(N, M, P) = list(map(int, input().split()))
e_list = []
for i in range(M):
	(A, B, C) = list(map(int, input().split()))
	(A, B) = (A - 1, B - 1)
	e_list.append((A, B, P - C))
vi = 0
min_dis_list = [10 ** 27] * N
min_dis_list[vi] = 0
for i in range(N - 1):
	for e in e_list:
		(u, v, d) = e
		if min_dis_list[v] > min_dis_list[u] + d:
			min_dis_list[v] = min_dis_list[u] + d
neg_loop_flag = [False] * N
for i in range(N):
	for e in e_list:
		(u, v, d) = e
		if min_dis_list[u] < 10 ** 26:
			if min_dis_list[u] + d < min_dis_list[v]:
				neg_loop_flag[v] = True
				min_dis_list[v] = min_dis_list[u] + d
			if neg_loop_flag[u]:
				neg_loop_flag[v] = True
if neg_loop_flag[N - 1]:
	print(-1)
else:
	print(max(0, -min_dis_list[N - 1]))


import sys
input = sys.stdin.buffer.readline
(n, m, p) = map(int, input().split())
es = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	es.append([a - 1, b - 1, -(c - p)])

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])
(temp, d) = find_negative_loop(0, n, m, es)
if temp == d:
	if temp > 0:
		print(0)
	else:
		print(-temp)
else:
	print(-1)


import sys
import math
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def I():
	return int(input())

def II():
	return map(int, input().split())

def III():
	return list(map(int, input().split()))

def Line(N):
	read_all = [tuple(map(int, input().split())) for _ in range(N)]
	return map(list, zip(*read_all))

def BF(E, s, n):
	inf = float('inf')
	d = [inf for _ in range(n)]
	d[s] = 0
	for i in range(2 * n):
		for e in E:
			if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				if i >= n:
					d[e[1]] = -float('inf')
	return d
(N, M, P) = II()
(A, B, C) = Line(M)
E = []
for i in range(M):
	E.append([A[i] - 1, B[i] - 1, -C[i] + P])
d = BF(E, 0, N)
if d[N - 1] == -float('inf'):
	print(-1)
else:
	print(max(0, -d[N - 1]))


ma = lambda : map(int, input().split())
lma = lambda : list(map(int, input().split()))
tma = lambda : tuple(map(int, input().split()))
ni = lambda : int(input())
yn = lambda fl: print('Yes') if fl else print('No')
import collections
import math
import itertools
import heapq as hq

def BF(graph, s):
	n = len(graph)
	INF = 10 ** 15
	dist = [INF] * n
	dist[s] = 0
	for _ in range(n - 1):
		for u in range(n):
			if dist[u] == INF:
				continue
			for (v, c) in graph[u]:
				if dist[v] > dist[u] + c:
					dist[v] = dist[u] + c
	for _ in range(n):
		for u in range(n):
			if dist[u] == INF:
				continue
			for (v, c) in graph[u]:
				if dist[v] > dist[u] + c:
					dist[v] = -INF
	return dist
(n, m, p) = ma()
G = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = ma()
	G[a - 1].append((b - 1, -c + p))
d = BF(G, 0)
if abs(d[-1]) == 10 ** 15:
	print(-1)
else:
	print(max(0, -d[-1]))


import sys
input = sys.stdin.readline
(N, M, P) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for _ in range(N)]
rs = [[] for _ in range(N)]
for (a, b, c) in ABC:
	(a, b) = (a - 1, b - 1)
	es[a].append(b)
	rs[b].append(a)
stack = [0]
vis_go = set([0])
while stack:
	v = stack.pop()
	for to in es[v]:
		if to in vis_go:
			continue
		vis_go.add(to)
		stack.append(to)
stack = [N - 1]
vis_bk = set([N - 1])
while stack:
	v = stack.pop()
	for to in rs[v]:
		if to in vis_bk:
			continue
		vis_bk.add(to)
		stack.append(to)
use = vis_go & vis_bk
INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(len(use)):
	for (a, b, c) in ABC:
		(a, b, c) = (a - 1, b - 1, P - c)
		if a not in use or b not in use:
			continue
		if dist[b] > dist[a] + c:
			dist[b] = dist[a] + c
			if i == len(use) - 1:
				print(-1)
				exit()
print(max(0, -dist[-1]))


(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])

def BellmanFord(edges, num_v, source):
	minus_flag = 0
	inf_flag = 0
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source - 1] = 0
	for i in range(num_v * 3):
		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:
					minus_flag = 1
				if minus_flag == 1:
					if edge[1] == N:
						inf_flag = 1
	if inf_flag == 0:
		return dist
	else:
		dist.append(-1)
		return dist
ans = BellmanFord(edges, N, 1)
if len(ans) != N:
	print(-1)
else:
	print(max(0, ans[-1] * -1))