module WeightedDirectedGraph
  (Weight : sig
    type t
    val inf : t
    val zero : t
    val neg_inf : t
    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
    d.(s) <- Weight.zero;
    for i = 1 to n - 1 do
      es.fold (fun (u, v, c) () ->
        let open Weight in
        (* c は u から v への辺の重さ *)
        (* d.(u) + c < d.(v) *)
        if 0 < Weight.compare d.(v) (d.(u) + c) then
          d.(v) <- d.(u) + c) ()
    done;
    (* 手動ループアンローリング *)
    for i = n to 2 * n do
      es.fold (fun (u, v, c) () ->
        let open Weight in
        if 0 < Weight.compare d.(v) (d.(u) + c) then
          (* n 回目以降に変更が起こった場合，v までの経路に負閉路が含まれている *)
          (d.(v) <- d.(u) + c; neg.(v) <- true)) ()
    done;
    fun v -> if neg.(v) then Weight.neg_inf else d.(v)
end

module G = WeightedDirectedGraph (struct
  type t = int
  let inf = -123456789012345678
  let zero = 0
  let neg_inf = 123456789012345678
  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
  let d = G.bellman_ford n { G.fold = fun f -> Array.fold_right f abcs } 0 (n - 1) in
  if 123456789012345678 <= d
  then print_endline "inf"
  else Printf.printf "%d\n" d
