#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
pub fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[allow(dead_code)]
pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
pub fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
pub fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}

}

use input::*;
use std::collections::{HashSet, VecDeque};

fn remove_edge(
    graph: &Vec<Vec<usize>>,
    graph_raw: &Vec<(usize, usize, isize)>,
) -> Vec<Vec<(usize, isize)>> {
    let mut ret = vec![Vec::new(); graph.len()];
    let mut set_v = HashSet::new();
    let mut queue = VecDeque::new();
    for v in &graph[graph.len() - 1] {
        queue.push_front(*v);
    }
    set_v.insert(graph.len() - 1);
    while !queue.is_empty() {
        let v = queue.pop_back().unwrap();
        set_v.insert(v);
        for v_next in &graph[v] {
            if !set_v.contains(v_next) {
                set_v.insert(*v_next);
                queue.push_front(*v_next);
            }
        }
    }

    for v in graph_raw {
        if set_v.contains(&v.1) {
            ret[v.0].push((v.1, v.2));
        }
    }
    ret
}

fn bellman_ford(graph: &Vec<Vec<(usize, isize)>>, ln: &mut Vec<Option<isize>>) -> bool {
    let mut inf_flag = false;
    for v in 0..graph.len() {
        for e in &graph[v] {
            let cost = e.1;
            let to = e.0;
            let from = v;
            if let Some(x) = ln[from] {
                if let None = ln[to] {
                    ln[to] = Some(x + cost);
                } else if let Some(y) = ln[to] {
                    if y < x + cost {
                        inf_flag = true;
                        ln[to] = Some(x + cost);
                    }
                }
            }
        }
    }
    inf_flag
}

fn main() {
    let (n, m, p): (usize, usize, isize);
    input!(n, m, p);

    let mut graph;
    let mut graph2 = vec![Vec::new(); n];
    let mut graph_raw = Vec::new();
    let mut longest = vec![None; n];
    longest[0] = Some(0);

    for _ in 0..m {
        let (a, b, c): (usize, usize, isize);
        input!(a, b, c);
        graph_raw.push((a - 1, b - 1, c - p));
        graph2[b - 1].push(a - 1);
    }

    graph = remove_edge(&graph2, &graph_raw);
    for _ in 0..n {
        bellman_ford(&graph, &mut longest);
    }
    if bellman_ford(&graph, &mut longest) {
        println!("-1");
    } else {
        println!("{}", std::cmp::max(0, longest[n - 1].unwrap()));
    }
}

Measured memory_bytes: 4476