import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as B

import           Control.Monad.ST
import           Data.Array.IArray
import           Data.Array.MArray
import           Data.Array.ST
import           Data.Array.Unboxed

readi :: B.ByteString -> Int
readi b | Just (n, _) <- B.readInt b = n

makeArray :: Int -> [(Int, Int, Int)] -> ST s (STUArray s (Int, Int) Int)
makeArray v xs = do
    a <- newArray ((0, 0), (v-1, v-1)) maxBound
    forM_ [0 .. v-1] $ \i -> writeArray a (i, i) 0
    forM_ xs $ \(s, t, d) -> writeArray a (s, t) d
    return a

updateArray :: STUArray s (Int, Int) Int -> ST s ()
updateArray a = do
    (_, (n, _)) <- getBounds a
    forM_ [0 .. n] $ \k -> do
        forM_ [0 .. n] $ \i -> do
            forM_ [0 .. n] $ \j -> do
                ij <- readArray a (i, j)
                ik <- readArray a (i, k)
                kj <- readArray a (k, j)
                if ik == maxBound || kj == maxBound
                    then return ()
                    else writeArray a (i, j) $ min ij (ik + kj)

hasNegativeCycle :: UArray (Int, Int) Int -> Bool
hasNegativeCycle a = any (< 0) $ fmap (a !) [(i, i) | i <- [0 .. n]]
  where
    (_, (n, _)) = bounds a

main :: IO ()
main = do
    [v, e] <- fmap readi . B.words <$> B.getLine
    xs <- replicateM e $ do
        [a, b, c] <- fmap readi . B.words <$> B.getLine
        return (a, b, c)

    let ary = runSTUArray $ do
            a <- makeArray v xs
            updateArray a
            return a

    let show_ x = if x == maxBound then "INF" else show x
    if hasNegativeCycle ary
        then putStrLn "NEGATIVE CYCLE"
        else do
            forM_ [0 .. v-1] $ \i -> do
                let ds = fmap (ary !) [(i, j) | j <- [0 .. v-1]]
                putStrLn . unwords $ fmap show_ ds

