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: interview

Starter code:

Solutions:
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)]
	tmp = []
	for a,b,c in zip(*[iter(L)]*3):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
		tmp+=[(a-1,b-1,P-c)]
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	ans = BellmanFord(N,[(a,b,c) for a,b,c in tmp if a in judge and b in judge])
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

def __starting_point():
	main()
__starting_point()

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

def belman(egdes, N, start, end):
    INF = int(1e10)
    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()

def validate(paths, start):
    """
    有効な経路をDFS(深さ優先探索)
    経路をsetで返す
    """

    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):
    """
    有向グラフ(負閉路有り)の最短距離

    num_v: 頂点の数(number_of_vertex)
    edges: 頂点(from, to, cost)
    """

    # グラフの初期化
    INF = 10**18
    dist = [INF] * num_v
    # 始点は0にする
    dist[start] = 0

    # 辺の緩和
    # 負の閉路が無ければ、num_v-1回までで収束する
    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:
        # num_v回の時に更新があるなら負閉路が存在する
        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):
        # 頂点nからの経路をdfsするため、辺の向きを逆にする
        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()

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

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

#!/usr/bin/env python3
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

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    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 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
  #G[a].append((b,c))
  A.append(a)
  B.append(b)
  C.append(c)
    
CC = [1] * len(A)
### https://atcoder.jp/contests/abc137/submissions/15987354
# とりあえず到達可能経路を探す、始点と終点から重み１にして辿っていき、双方登場した点が探すべき点。
# directedなので、A,Bを入れ替えているところもポイント
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))
  #csr_mat.data = P - csr_mat.data
  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
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 # 自身への距離は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()

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)

    def reachable(E, a):
        S = {a}
        stack = [a]
        while stack:
            s = stack.pop()
            for v in E[s]:
                if v not in S:
                    stack.append(v)
                    S.add(v)
        return S

    ok = reachable(F, 0) & reachable(B, N - 1)

    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

    print((-1 if bellman_ford(N + 1) else max(-D[-1], 0)))


def __starting_point():
    main()

__starting_point()

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


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(len(U)):
        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 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])))


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

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

def __starting_point():
	main()
__starting_point()

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)

# N-1→0の辺を追加してから強連結判定⇒ゴールにたどり着けない閉路を除外
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 = []
edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = list(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
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()

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

    print((-1 if bellman_ford(N + 1) else max(-D[-1], 0)))


def __starting_point():
    main()

__starting_point()

import collections

n, m, p = list(map(int, input().split()))
dist1 = []
edges1 = [[] for _ in range(n)]
edges2 = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = list(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)))


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

abc = []
# edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = list(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(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
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()

# 頂点sから到達する頂点の集合
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):
    # コストをINFで初期化
    d = [10**18] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:break
    else:
        # V回目まで更新があったら負の閉路がある
        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)
        # 頂点Nからdfsするため辺の向きを逆にする
        edge_rev[b-1].append(a-1)
        e.append((a-1, b-1, p-c))
    # 頂点1と頂点Nのどちらからも到達できる頂点の集合
    use = dfs(edge, 0) & dfs(edge_rev, n-1)
    # fromとtoがどちらもuseに含まれる辺のみ使う
    # そうすることで負の閉路を検出した場合答えは必ず-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 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()

# 到達可能な頂点の集合
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
  # 負の閉路が無ければ更新はV-1回までで終わる
  for _ in range(num):
    updated = False
    for a, b, c in edges:
      # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
      if cost[b] > cost[a]+c:
        cost[b] = cost[a]+c
        updated = True
    if not updated: break
  else:
    # V回目まで更新があったら負の閉路がある
    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))

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

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

def glaph_bfs(s,n,e):
  ans=[0]*n
  Q=[s]
  visited={s}
  while Q:
    P=[]
    for i in Q:
      ans[i]=1
      for j in e[i]:
        if j in visited:continue
        visited.add(j)
        P.append(j)
    Q=P
  return ans

n,m,p=map(int,input().split())
ef=[[]for _ in range(n)]
ee=[[]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)
  e.append((a,b,c))
eff=glaph_bfs(0,n,ef)
eef=glaph_bfs(n-1,n,ee)
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))

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print((max(a+b,a-b,a*b)))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print((*ans))
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in list(d.values()):
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

#E
def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print((-1))
    elif ans < 0:
        print((0))
    else:
        print(ans)
    return

#F
def F():

    return

#Solve
def __starting_point():
    E()

__starting_point()

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)

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
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:
            break
    else:
        # V回目まで更新があったら負の閉路がある
        print((-1))
        return
    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
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)]  # rev_edge
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 = bfs(edge1, 0) & bfs(edge2, n-1)
dist2 = [(a,b,c) for a,b,c in dist if a in use and b in use]
print(bellman(dist2))

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


# Coins Respawn
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]))

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

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

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


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


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

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


from collections import deque
import math

n,m,p = map(int, input().split())
dist  = []
edge1 = [[] for _ in range(n)]
edge2 = [[] for _ in range(n)]  # rev_edge
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)   

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)     
    
use = bfs(edge1, 0) & bfs(edge2, n-1)
dist2 = [(a,b,c) for a,b,c in dist if a in use and b in use]
print(bellman(dist2))

# https://atcoder.jp/contests/abc137/tasks/abc137_e
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))

    # Only consider nodes that can be reached from 1 and can reach N.
    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()

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

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

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

#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)

#負の閉路検出
#n=頂点数 e=[[a,b,c],[]...](a~bの距離がc)
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)

#DAG判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
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))

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):
    #goal = n-1
    used = {goal}
    q = [goal]
    while q:
        v = q.pop()
        for w in edge[v]:
            if w in used:continue
            used.add(w)
            q.append(w)
    
    return used

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

    '''
    v: vertex(頂点)
    s: start.  in this case,0
    g: goal. in this case,n-1
    e: (edge_start,egde_goal,score)
    今回はp-cの最小値を求めていく.
    '''
    inf = 10**10
    # cost : d[V] 
    d = [inf] * v
    #開始点のコストを0とする
    d[s] = 0
    for _ in range(v):
        flag = False
        for a,b,c in e:
            # a -> b の向きを考える
            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_)))


#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print((max(a+b,a-b,a*b)))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print((*ans))
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in list(d.values()):
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

#E
def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print((-1))
    elif ans < 0:
        print((0))
    else:
        print(ans)
    return

#F
def F():

    return

#Solve
def __starting_point():
    E()

__starting_point()