import collection.mutable.ArrayBuffer

trait graph {
   import scala.reflect.ClassTag
   case class Edge[T](from : Int, to : Int, cost : T)
   type Edges[T] = ArrayBuffer[Edge[T]]
   def Edges[T](xs : Edge[T]*) = ArrayBuffer(xs : _*)
   type WeightedGraph[T] = ArrayBuffer[Edges[T]]
   def WeightedGraph[T](size : Int) = ArrayBuffer.fill(size)(Edges[T]())
   type UnWeightedGraph = ArrayBuffer[Edges[Int]]
   type Matrix[T] = Array[Array[T]]
   def Matrix[T:Numeric:ClassTag](row : Int, col : Int) : Matrix[T] = {
       val zero: T = implicitly[Numeric[T]].zero
       Array.fill(row, col)(zero)
   }
   def Matrix[T:Numeric:ClassTag](row : Int, col : Int, init : T) : Matrix[T] = {
       Array.fill(row, col)(init)
   }
   def Matrix[T:Numeric:ClassTag](size : Int) : Matrix[T] = Matrix(size, size)
   def Matrix[T:Numeric:ClassTag](size : Int, init : T) : Matrix[T] = Matrix(size, size, init)
}

object WarshallFloyd extends graph {
    def warshallFloyd(g : Matrix[Int], V : Int) = {
        val dist = g.clone
        for (i <- 0 until V) dist(i)(i) = 0
        for (k <- 0 until V) {
            for (i <- 0 until V) {
                for (j <- 0 until V 
                    if dist(i)(k) != Int.MaxValue 
                    && dist(k)(j) != Int.MaxValue) {
                    dist(i)(j) = dist(i)(j) min dist(i)(k) + dist(k)(j)
                }
            }
        }
        dist
    }
}


import WarshallFloyd._

object Main {
    def main(args: Array[String]) = {
        val sc = new java.util.Scanner(System.in)
        val V, E = sc.nextInt
        val mat = Matrix[Int](V, init = Int.MaxValue)
        for (_ <- 1 to E) {
            val s, t, c = sc.nextInt
            mat(s)(t) = c
        }
        val res = warshallFloyd(mat, V)
        var flag = true
        for (i <- 0 until res.size if flag) {
            if (res(i)(i) < 0) {
                flag = false
            }
        }
        if (!flag) {
            println("NEGATIVE CYCLE")
        } else {
            for (r <- res) {
                for (i <- 0 until r.size) {
                    if (i > 0) print(" ")
                    if (r(i) == Int.MaxValue) print("INF")
                    else print(s"${r(i)}")
                }
                println("")
            }
        }
    }
}
