use std::io::Read;
trait BinarySearch<T> {
    fn front_position(&self, x: T) -> usize;
    fn back_position(&self, x: T) -> usize;
    fn bs_position(v: &[T], x: T, is_back: bool) -> usize;
}

impl<T> BinarySearch<T> for Vec<T>
where
    T: Ord,
{
    fn front_position(&self, x: T) -> usize {
        if self.is_empty() {
            return 0;
        }
        Self::bs_position(self, x, true)
    }

    fn back_position(&self, x: T) -> usize {
        if self.is_empty() {
            return 0;
        }
        Self::bs_position(self, x, false)
    }

    fn bs_position(v: &[T], x: T, is_front: bool) -> usize {
        let len = v.len();
        if len == 1 {
            return if x < v[0] || (is_front && x == v[0]) {
                0
            } else {
                1
            };
        }
        let i = len / 2;
        if x < v[i] || (is_front && x == v[i]) {
            Self::bs_position(&v[..i], x, is_front)
        } else {
            Self::bs_position(&v[i..], x, is_front) + i
        }
    }
}

pub fn read_stdin() -> String {
    let mut s = String::new();
    ::std::io::stdin().read_to_string(&mut s).unwrap();
    s
}

pub trait Parse {
    fn to<T>(&mut self) -> T
    where
        T: std::str::FromStr;
}

impl<'a> Parse for std::str::SplitWhitespace<'a> {
    fn to<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let word = self.next().unwrap();
        word.parse().ok().unwrap()
    }
}

fn dfs(src: usize, dest: usize, reached: &mut Vec<bool>, adj: &Vec<Vec<usize>>) -> bool {
    for &i in &adj[src] {
        if i == dest {
            return true;
        }
        if !reached[i] {
            reached[i] = true;
            if dfs(i, dest, reached, adj) {
                return true;
            }
        }
    }
    false
}

fn is_reachable(src: usize, dest: usize, adj: &Vec<Vec<usize>>) -> bool {
    let mut reached = vec![false; adj.len()];
    reached[src] = true;
    dfs(src, dest, &mut reached, adj)
}

type Edge = (usize, usize, i64);
fn bellman_ford(n: usize, edges: Vec<Edge>) -> (Vec<Option<i64>>, Vec<Option<usize>>, Vec<usize>) {
    let mut prev = vec![None; n];
    let mut xs = vec![None; n];
    let mut cycle = Vec::new();
    xs[0] = Some(0);

    for k in 0..n {
        for &e in &edges {
            if let Some(x1) = xs[e.1] {
                if let Some(x0) = xs[e.0] {
                    let x = x0 + e.2;
                    if x1 < x {
                        xs[e.1] = Some(x);
                        prev[e.1] = Some(e.0);
                        if k == n - 1 {
                            cycle.push(e.1);
                        }
                    }
                }
            } else {
                if let Some(x0) = xs[e.0] {
                    xs[e.1] = Some(x0 + e.2);
                    prev[e.1] = Some(e.0);
                    if k == n - 1 {
                        cycle.push(e.1);
                    }
                }
            }
        }
    }
    cycle.sort();
    (xs, prev, cycle)
}

fn check_cycle(
    (xs, prev, cycle): (Vec<Option<i64>>, Vec<Option<usize>>, Vec<usize>),
    adj: &Vec<Vec<usize>>,
) -> i64 {
    let mut path = Vec::new();
    let n = xs.len();
    let mut u = prev[n - 1];
    while let Some(i) = u {
        let j = path.front_position(i);
        if j < path.len() && path[j] == i {
            return -1;
        }
        path.insert(j, i);
        u = prev[i];
    }

    for c in cycle {
        if is_reachable(c, n - 1, adj) {
            return -1;
        }
    }

    std::cmp::max(0, xs.last().unwrap().unwrap())
}

fn main() {
    let source = read_stdin();
    let mut iter = source.split_whitespace();
    let n = iter.to();
    let m = iter.to();
    let p: i64 = iter.to();
    let v = (0..m)
        .map(|_| {
            (
                iter.to::<usize>() - 1,
                iter.to::<usize>() - 1,
                iter.to::<i64>() - p,
            )
        })
        .collect::<Vec<_>>();
    let mut adj = vec![Vec::new(); n];
    for &edge in &v {
        adj[edge.0].push(edge.1);
    }

    println!("{}", check_cycle(bellman_ford(n, v), &adj));
}

Measured memory_bytes: 4476