module CoordComp
  (* 座標の型 *)
  (Coord : sig
    type t
    val compare : t -> t -> int
  end) :
sig
  val compress :
    (* 座標のリスト *)
    Coord.t list ->
    (* 座標の数，圧縮する関数と解凍する関数を返す *)
    int * (Coord.t -> int) * (int -> Coord.t)
end = struct
  module IntMap = Map.Make (struct
    type t = int
    let compare = compare
  end)
  module CoordMap = Map.Make (Coord)

  let compress cs =
    let (n, comp, decomp) =
      List.fold_left (fun (n, comp, decomp) c ->
        if CoordMap.mem c comp then (n, comp, decomp)
        else (n + 1, CoordMap.add c n comp, IntMap.add n c decomp))
      (0, CoordMap.empty, IntMap.empty) cs in
    (n, (fun c -> CoordMap.find c comp), (fun n -> IntMap.find n decomp))
end

(* 無限大の要素を付け足してトロピカル半環を作る *)
module WithInf
  (S : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  (* Noneで無限大を表す *)
  type t = S.t option
  val inf : t
  val zero : t
  val ( + ) : t -> t -> t
  val compare : t -> t -> int
end =
struct
  type t = S.t option
  let inf = None
  let zero = Some S.zero
  let ( + ) x y =
    match x, y with
    | None, _ -> None
    | _, None -> None
    | Some m, Some n -> Some (S.( + ) m n)
  let compare x y =
    match x, y with
    | None, None -> 0
    | None, _ -> 1
    | _, None -> -1
    | Some m, Some n -> S.compare m n
end


module WeightedDirectedGraph
  (Vertex : sig
    type t
    val compare : t -> t -> int
  end)
  (Weight : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  (* 配列版の実装 *)
  val raw_bellman_ford :
    (* 頂点数n *)
    int ->
    (* 辺のリスト *)
    (* 頂点は0からn-1までの整数でなくてはならない *)
    (int * int * Weight.t) list ->
    (* 始点 *)
    int ->
    (int -> [ `Weight of Weight.t | `Inf | `NegInf ])

  (* 座標圧縮により様々な型を使えるようにしたバージョン *)
  val bellman_ford :
    (* 辺のリスト *)
    (Vertex.t * Vertex.t * Weight.t) list ->
    (* 始点 *)
    Vertex.t ->
    (Vertex.t -> [ `Weight of Weight.t | `Inf | `NegInf ])
end =
struct
  module CC = CoordComp (Vertex)
  module Weight' = WithInf (Weight)

  let raw_bellman_ford n es s =
    (* 距離を覚えるやつ *)
    (* Noneで無限を表す *)
    let d = Array.make n None in
    (* 経路に負閉路が含まれる頂点を覚えるやつ *)
    let neg = Array.make n false in
    d.(s) <- Some Weight.zero;
    for i = 0 to 2 * n - 1 do
      List.iter (fun (u, v, c) ->
        let open Weight' in
        (* c は u から v への辺の重さ *)
        (* d.(u) + c < d.(v) *)
        if 0 < compare d.(v) (d.(u) + Some c) then begin
          d.(v) <- d.(u) + Some c;
          if n - 1 <= i then
            (* n 回目以降に変更が起こった場合，v までの経路に負閉路が含まれている *)
            neg.(v) <- true
        end) es
    done;
    fun v ->
      if neg.(v) then `NegInf
      else
        match d.(v) with
        | None -> `Inf
        | Some d -> `Weight d

  let bellman_ford es s =
    let (n, comp, _) =
      CC.compress @@
        List.concat @@
          List.map (fun (u, v, _) -> [u; v]) es in
    match 
      raw_bellman_ford n
        (List.map (fun (u, v, c) -> (comp u, comp v, c)) es) (comp s)
    with
    | exception Not_found -> (* 頂点から延びる辺がない *)
        fun _ -> `Inf
    | d ->
        fun v -> try d (comp v) with Not_found -> `Inf
end


 
module Int = struct
  type t = int
  let zero = 0
  let ( + ) = ( + )
  let compare x y = compare y x
end
 
module G = WeightedDirectedGraph (Int) (Int)
 
let () = Scanf.scanf "%d %d\n" (fun n m ->
  let abcs = Array.init m (fun _ -> Scanf.scanf "%d %d %d\n" (fun a b c -> a - 1, b - 1, c)) in
  match G.bellman_ford (Array.to_list abcs) 0 (n - 1) with
  | `NegInf -> print_endline "inf"
  | `Weight c -> Printf.printf "%d\n" c)


Measured memory_bytes: 5376