object Main{
  def warshallfloyd(graph : Array[Array[Long]]) : Array[Array[Long]] = {
    val d = graph.map(_.clone)
    val V = graph.length
    for(k <- 0 until V; i <- 0 until V; j <- 0 until V){
      d(i)(j) = d(i)(j).min(d(i)(k)+d(k)(j))
    }
    return d
  }

  def main(args:Array[String]){
    val sc = new java.util.Scanner(System.in)
    val V,E = sc.nextInt

    val g = Array.fill[Long](V,V)(Long.MaxValue / 10)
    for(i <- 0 until V) g(i)(i) = 0

    for(i <- 0 until E){
      val s,t,d = sc.nextInt
      g(s)(t) = d
    }

    val res = warshallfloyd(g)
    val res2 = warshallfloyd(res)

    var flag = true
    for(i <- 0 until V; j<- 0 until V){
      if(res2(i)(j) < res(i)(j)){
        println("NEGATIVE CYCLE")
        flag = false
      }
    }

    if(flag){
      for(i <- 0 until V){
        for(j <- 0 until V){
          if(j!=0) print(" ")
          print(if(res(i)(j) != Long.MaxValue/10) res(i)(j) else "INF")
        }
        println()
      }
    }
  }
}