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)

  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) ->
        (* c は u から v への辺の重さ *)
        (* d.(v) <- min d.(v) (d.(u) + c) *)
        let open Weight in
        match d.(v), d.(u) with
        | _, None -> () (* d.(u) は無限大 *)
        (* d.(v) <= d.(u) + c *)
        | Some dv, Some du when compare dv (du + c) <= 0 -> ()
        | _, Some du ->
            d.(v) <- Some (du + c);
              (* n 回目以降に変更が起こった場合，v までの経路に負閉路が含まれている *)
              if n - 1 <= i then
                neg.(v) <- true) 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
    let d =
      raw_bellman_ford n
        (List.map (fun (u, v, c) -> (comp u, comp v, c)) es) (comp s) in
    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)