{-# LANGUAGE FlexibleContexts #-}
import Data.Array
import Data.Array.ST

data Point = Neginf | Fin Int deriving (Eq,Show)
instance Ord Point where
  compare Neginf  Neginf = EQ
  compare (Fin _) Neginf = GT
  compare Neginf (Fin _) = LT
  compare (Fin a) (Fin b)= compare a b

type W_graph = Array (Int,Int) Point

get_graph::Int -> [(Int,Int,Int)] -> W_graph
get_graph n dat = runSTArray $ do
  ar<-newArray ((1,1),(n,n)) Neginf
  mapM_ (writer ar) dat
  mapM_ (diag   ar) [1..n]
  return ar
      where writer ar (a,b,w) = do
                        writeArray ar (a,b) (Fin w)
            diag   ar j       = do
                        writeArray ar (j,j) (Fin 0)

plus::Point -> Point -> Point
plus Neginf _ = Neginf
plus _ Neginf = Neginf
plus (Fin a) (Fin b) = Fin (a+b)

bellman_ford_maximize::Int -> W_graph -> Maybe Point
bellman_ford_maximize n gr =  let init_ar = listArray (1,n) ((Fin 0):(take (n-1) (repeat Neginf))) in
                              let n_looped = n_proped n gr init_ar n in
                              if propagate n gr n_looped == n_looped then Just (n_looped!n) else Nothing

propagate::Int -> W_graph -> Array Int Point -> Array Int Point
propagate n gr ar = listArray (1,n) [(maximum [plus (ar!j) (gr!(j,i))|j<-[1..n]])|i<-[1..n]]

n_proped::Int -> W_graph -> Array Int Point -> Int -> Array Int Point
n_proped n gr ar 0 = ar
n_proped n gr ar m = let ar_ = propagate n gr ar in n_proped n gr ar_ (m-1)


n_get::Int ->IO [(Int,Int,Int)]
n_get 0 =return []
n_get n =do
  d<-getLine
  let a:b:w:[]= map read (words d)
  rest <- n_get (n-1)
  return ((a,b,w):rest)

main::IO()
main=do
  nmc<-getLine
  let n:m:[]=map read (words nmc)::[Int]
  dat<-n_get m
  let gr = get_graph n dat
  do case bellman_ford_maximize n gr of
            Nothing      -> putStr "inf\n"
            Just (Fin x) -> print x