module WeightedDirectedGraph
  (Weight : sig
    type t
    val inf : t (* オーバーフローの恐れはないので，max_intとか突っ込んでも良い *)
    val zero : t
    val neg_inf : t (* オーバーフローの恐れはないので，min_intとか突っ込んでも良い *)
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  type 'a church_list = { fold : 'b. ('a -> 'b -> 'b) -> 'b -> 'b }

  val bellman_ford :
    (* 頂点数n *)
    int ->
    (* 辺のリスト
       頂点は0からn-1までの整数でなくてはならない
       2n回呼び出されるので，リストを作るのに時間がかかるならメモ化すること *)
    (int * int * Weight.t) church_list ->
    (* 始点 *)
    int ->
    (* 頂点を受け取り，そこまでの距離を返す関数
       頂点に到達するパスが無ければinfを返し，
       そこに到達するまでに負閉路があればneg_infを返す *)
    (int -> Weight.t)
end =
struct
  type 'a church_list = { fold : 'b. ('a -> 'b -> 'b) -> 'b -> 'b }

  let bellman_ford n es s =
    (* 距離を覚えるやつ *)
    let d = Array.make n Weight.inf in
    (* 経路に負閉路が含まれる頂点を覚えるやつ *)
    let neg = Array.make n false in
    (* 始点より終点のインデックスが大きくなる辺を集めた隣接リスト *)
    let inc = Array.make n [] in
    (* 始点より終点のインデックスが小さくなる辺を集めた隣接リスト *)
    let dec = Array.make n [] in
    es.fold (fun (u, v, c) () ->
      if u <= v
      then inc.(u) <- (v, c) :: inc.(u)
      else dec.(u) <- (v, c) :: dec.(u)) ();
    d.(s) <- Weight.zero;
    (* 残りの反復回数 *)
    let i = ref (n / 2) in
    (* 更新が行われたか *)
    let is_modified = ref true in
    while 0 < !i && !is_modified do
      is_modified := false;
      (* インデックスが増加する辺の処理 *)
      for u = 0 to n - 1 do
        List.iter (fun (v, c) ->
          let open Weight in
          if
            (* 原点から到達できない頂点は更新しない *)
            0 < Weight.compare inf d.(u)
            (* c は u から v への辺の重さ
               d.(u) + c < d.(v) *)
            && 0 < Weight.compare d.(v) (d.(u) + c)
          then (d.(v) <- d.(u) + c; is_modified := true)) inc.(u)
      done;
      (* インデックスが減少する辺の処理 *)
      for u = n - 1 downto 0 do
        List.iter (fun (v, c) ->
          let open Weight in
          if 0 < Weight.compare inf d.(u) && 0 < Weight.compare d.(v) (d.(u) + c)
          then (d.(v) <- d.(u) + c; is_modified := true)) dec.(u);
      done;
      decr i
    done;
    (* 負閉路を見付けるループ *)
    i := (n + 1) / 2;
    while 0 < !i && !is_modified do
      is_modified := false;
      (* インデックスが増加する辺の処理 *)
      for u = 0 to n - 1 do
        List.iter (fun (v, c) ->
          if neg.(u) then neg.(v) <- true;
          let open Weight in
          if 0 < Weight.compare inf d.(u) && 0 < Weight.compare d.(v) (d.(u) + c)
          then (d.(v) <- d.(u) + c; neg.(v) <- true; is_modified := true)) inc.(u)
      done;
      (* インデックスが減少する辺の処理 *)
      for u = n - 1 downto 0 do
        List.iter (fun (v, c) ->
          if neg.(u) then neg.(v) <- true;
          let open Weight in
          if 0 < Weight.compare inf d.(u) && 0 < Weight.compare d.(v) (d.(u) + c)
          then (d.(v) <- d.(u) + c; neg.(v) <- true; is_modified := true)) dec.(u);
      done;
      decr i
    done;
    fun v -> if neg.(v) then Weight.neg_inf else d.(v)
end

module G = WeightedDirectedGraph (struct
  type t = int
  let zero = 0
  let inf = min_int
  let neg_inf = max_int
  let ( + ) = ( + )
  let compare x y = compare y x
end)

let () = Scanf.scanf "%d %d %d\n" @@ fun n m p ->
  let abc = Array.init m @@ fun _ ->
    Scanf.scanf "%d %d %d\n" @@ fun a b c -> a - 1, b - 1, c - p in
  let d = G.bellman_ford n { G.fold = fun f -> Array.fold_right f abc } 0 (n - 1) in
  if max_int <= d
  then print_endline "-1"
  else Printf.printf "%d\n" @@ max 0 d


Measured memory_bytes: 5248