import sys

sys.setrecursionlimit(10**6)



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



edges = []

routes  = [[] for i in range(n)]

rev_routes = [[] for i in range(n)]

from_start = set()

to_goal = set()



def dfs(node, routes, seen):

    if node in seen:

        return

    seen.add(node)

    candidates = routes[node]

    for to in candidates:

        dfs(to, routes, 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)



dfs(0, routes, from_start)

dfs(n-1, rev_routes, to_goal)



from_start_to_goal = from_start & to_goal



graph = [-float('INF')] * n

graph[0] = 0



for i in range(n):

    is_updated = False

    for node, to, value in edges:

        if node not in from_start_to_goal or to not in from_start_to_goal:

            continue

        current_point = graph[node]

        next_point = graph[node] + value

        if graph[to] < next_point:

            graph[to] = next_point

            is_updated = True

        else:

            continue

    if not is_updated:

        score = max(0, graph[n-1])

        break

else:

    score = -1

      

print(score)

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





if __name__ == "__main__":

    main()

import sys

sys.setrecursionlimit(10**6)
n, m, p = list(map(int, input().split()))
edges = []
routes = [[] for i in range(n)]
rev_routes = [[] for i in range(n)]
from_start = set()
to_goal = set()


def dfs(node, routes, seen):
    if node in seen:
        return
    seen.add(node)
    candidates = routes[node]
    for to in candidates:
        dfs(to, routes, 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)
dfs(0, routes, from_start)
dfs(n - 1, rev_routes, to_goal)
from_start_to_goal = from_start & to_goal
graph = [-float("INF")] * n
graph[0] = 0
for i in range(n):
    is_updated = False
    for node, to, value in edges:
        if node not in from_start_to_goal or to not in from_start_to_goal:
            continue
        current_point = graph[node]
        next_point = graph[node] + value
        if graph[to] < next_point:
            graph[to] = next_point
            is_updated = True
        else:
            continue
    if not is_updated:
        score = max(0, graph[n - 1])
        break
else:
    score = -1
print(score)

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


if __name__ == "__main__":
    main()

+from scipy.sparse import coo_matrix +from scipy.sparse.csgraph import bellman_ford, NegativeCycleError -sys.setrecursionlimit(10**6) -n, m, p = list(map(int, input().split())) -edges = [] -routes = [[] for i in range(n)] -rev_routes = [[] for i in range(n)] -from_start = set() -to_goal = set() +input = sys.stdin.readline -def dfs(node, routes, seen): -    if node in seen: +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)) -    seen.add(node) -    candidates = routes[node] -    for to in candidates: -        dfs(to, routes, seen) +    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)) -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) -dfs(0, routes, from_start) -dfs(n - 1, rev_routes, to_goal) -from_start_to_goal = from_start & to_goal -graph = [-float("INF")] * n -graph[0] = 0 -for i in range(n): -    is_updated = False -    for node, to, value in edges: -        if node not in from_start_to_goal or to not in from_start_to_goal: -            continue -        current_point = graph[node] -        next_point = graph[node] + value -        if graph[to] < next_point: -            graph[to] = next_point -            is_updated = True -        else: -            continue -    if not is_updated: -        score = max(0, graph[n - 1]) -        break -else: -    score = -1 -print(score) +if __name__ == "__main__": +    main()