def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end


def min(a,b)
  return a>b ? b : a
end
V,E=get_i
d=Array.new(V).map{Array.new(V){Float::INFINITY}}
V.times do|i|
  d[i][i]=0
end
E.times do|i|
  s,t,d_=get_i
  d[s][t]=d_
end

V.times do|k|
  V.times do|i|
    V.times do|j|
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    end
  end
end
flag=false
V.times do|i|
  if d[i][i]<0
    flag=true
    break
  end
end
if flag
  puts "NEGATIVE CYCLE"
else
  V.times do|i|
    V.times do|j|
      if d[i][j]==Float::INFINITY
        print "INF"
      else
        print d[i][j]
      end
      print " " unless j==V-1
    end
    print "\n"
  end
end
