import qualified Data.ByteString.Lazy.Char8 as B
import qualified Data.Map.Strict as M
import Control.Applicative
import Data.List

chunksOf :: Int -> [a] -> [[a]]
chunksOf n = takeWhile (not . null) . unfoldr (return . splitAt n)

main = do
  [v,e] <- map read . words <$> getLine
  es <- readDirectedEdge <$> B.getContents
  let memo = warshallFloyd v es
  let r = chunksOf v [maybe "INF" show (M.lookup (i,j) memo) | i<-[0..v-1], j<-[0..v-1]]
  if all (>=0) [maybe 0 id (M.lookup (i,i) memo) | i<-[0..v-1]]
    then mapM_ (putStrLn . unwords) r
    else putStrLn "NEGATIVE CYCLE"

type Memo = M.Map (Vertex, Vertex) Weight

warshallFloyd :: Int -> [Edge] -> Memo
warshallFloyd n es = foldl shorten m0 kij
  where
    m0 = M.fromList (es ++ [((i,i),0) | i <-[0 .. n-1]])
    kij = [(k, i, j) | k <- [0 .. n-1], i <- [0 .. n-1], j <- [0 .. n-1]]

shorten :: Memo -> (Vertex, Vertex, Vertex) -> Memo
shorten m (k, i, j) = case connect m k i j of
  Nothing -> m
  Just w -> M.insertWith min (i, j) w m

connect :: Memo -> Vertex -> Vertex -> Vertex -> Maybe Weight
connect m k i j = do
  w1 <- M.lookup (i, k) m
  w2 <- M.lookup (k, j) m
  return (w1 + w2)

readInt :: B.ByteString -> Int
readInt = maybe undefined fst . B.readInt

type Vertex = Int
type Weight = Int
type Edge = ((Vertex, Vertex), Weight)

readDirectedEdge :: B.ByteString -> [Edge]
readDirectedEdge = map (constructOneWay . map readInt . B.words) . B.lines

constructOneWay :: [Int] -> Edge
constructOneWay [s,t,w] = ((s, t), w)
constructOneWay _ = undefined