module WeightedDirectedGraph
  (Weight : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  val bellman_ford :
    (* 頂点数 *)
    int ->
    (* 辺のリスト *)
    ('v * 'v * Weight.t) list ->
    (* 始点 *)
    'v ->
    ('v -> [ `Weight of Weight.t | `Inf | `NegInf ])
end =
struct
  let bellman_ford n es s =
    (* 距離を覚えるやつ *)
    (* d に入っていない頂点への距離は無限大とみなす *)
    let d = Hashtbl.create n in
    (* 負閉路に含まれる頂点を覚えるやつ *)
    (* 負閉路に含まれている iff neg に含まれる *)
    let neg = Hashtbl.create n in
    Hashtbl.replace d s Weight.zero;
    for i = 0 to 2 * n - 1 do
      List.iter (fun (u, v, c) ->
        (* c は u から v への辺の重さ *)
        (* d.(v) <- min d.(v) (d.(u) + c) *)
        let open Weight in
        match Hashtbl.find d u with
        | exception Not_found -> () (* d.(u) は無限大 *)
        | du ->
            (* d.(v) > d.(u) + c *)
            if
              try 0 < compare (Hashtbl.find d v) (du + c)
              with Not_found -> true (* d.(v) は無限大 *)
            then begin
              Hashtbl.replace d v (du + c);
              if n - 1 <= i then
                Hashtbl.replace neg v ()
            end) es
    done;
    fun v ->
      if Hashtbl.mem neg v then `NegInf
      else try `Weight (Hashtbl.find d v) with Not_found -> `Inf
end

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

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 n (Array.to_list abcs) 0 (n - 1) with
  | `NegInf -> print_endline "inf"
  | `Weight c -> Printf.printf "%d\n" c)