output_description: If the graph contains a negative cycle (a cycle whose sum of edge costs is a
  negative value), print
  
      
      
      NEGATIVE CYCLE
      
  
  in a line.
  
  Otherwise, print
  
      
      
      D0,0 D0,1 ... D0,|V|-1
      D1,0 D1,1 ... D1,|V|-1
      :
      D|V|-1,0 D1,1 ... D|V|-1,|V|-1
      
  
  The output consists of |V| lines. For each ith line, print the cost of the
  shortest path from vertex i to each vertex j (j = 0, 1, ... |V|-1)
  respectively. If there is no path from vertex i to vertex j, print "INF".
  Print a space between the costs.
input_description: An edge-weighted graph G (V, E).
  
      
      
      |V| |E|
      s0 t0 d0
      s1 t1 d1
      :
      s|E|-1 t|E|-1 d|E|-1
      
  
  |V| is the number of vertices and |E| is the number of edges in G. The graph
  vertices are named with the numbers 0, 1,..., |V|-1 respectively.
  
  si and ti represent source and target vertices of i-th edge (directed) and di
  represents the cost of the i-th edge.
attempt: # http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja
  # Johnsonのアルゴリズム
  # Bellman-Ford法で負辺を消去した後、
  # 各頂点からダイクストラを行う
  from heapq import heappop, heappush
  import sys
  
  read = sys.stdin.read
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines
  
  
  class BellmanFord:
      """
      shortest_distance(): startノードから各ノードまでの最短距離
      include_negative_cycle(): 負閉路の存在確認
      """
  
      def __init__(self, V, edges, start):
          """
          V : 頂点数
          edges: (辺の始点,辺の終点,辺のコスト)を要素とする辺のリスト
          start: 始点のノード番号
          """
          self.V = V
          self.edges = edges
          self.start = start
  
      def include_negative_cycle(self):
          """
          負閉路の存在確認
          Returns: True or False
          """
          d = [0] * self.V
          for i in range(self.V):
              # start, end, cost
              for s, e, c in self.edges:
                  if d[e] > d[s] + c:
                      d[e] = d[s] + c
                      # V回目にも更新があるなら負の閉路が存在する
                      if i == self.V - 1:
                          return True
          return False
  
      def shortest_distance(self):
          """
          始点から各頂点までの最短距離をを返す
          負閉路に到達可能ならば d[start] = INF
          """
          d = [float("inf")] * self.V
          d[self.start] = 0
  
          loop_counter = 0
          while True:
              update = False
              # start, end, cost
              for s, e, c in self.edges:
                  if d[s] != float("inf") and d[e] > d[s] + c:
                      d[e] = d[s] + c
                      update = True
  
              # 負閉路の到達しないならばループは高々V-1回
              # ループ回数がV回の時点で更新があるならば負閉路に到達してしまう
              loop_counter += 1
              if loop_counter == self.V and update:
                  d[self.start] = float("inf")
                  break
  
              if not update:
                  break
  
          return d
  
  
  class Dijkstra:
      """
      shortest_distance(): startノードから各ノードまでの最短距離
      """
  
      def __init__(self, graph, start):
          """
          graph: 隣接リストによるグラフ
          start: 始点のノード番号
          """
          self.g = graph
          self.V = len(graph)
  
          # startノードからの最短距離
          # startノードは0, それ以外は無限大で初期化
          self.dist = [float("inf")] * self.V
          self.dist[start] = 0
  
          # startノードをキューに入れる
          self.Q = []
          heappush(self.Q, (0, start))
  
          while self.Q:
              # 優先度（距離）が最小であるキューを取り出す
              dist_u, u = heappop(self.Q)
              if dist_u > self.dist[u]:
                  continue
              for v, weight in self.g[u]:
                  alt = self.dist[u] + weight
                  if alt < self.dist[v]:
                      self.dist[v] = alt
                      heappush(self.Q, (alt, v))
  
      def shortest_distance(self):
          return self.dist
  
  
  def main():
      V, E, *std = map(int, read().split())
  
      Edges = []
      for i in range(V):
          Edges.append((V, i, 0))
  
      for s, t, d in zip(*[iter(std)] * 3):
          Edges.append((s, t, d))
  
      # 超頂点からBellman-Ford O(VE)
      bf = BellmanFord(V + 1, Edges, V)
      h = bf.shortest_distance()
  
      if float("inf") in h:
          print("NEGATIVE CYCLE")
      else:
          Graph = [[] * V for _ in range(V)]
          for s, t, d in Edges:
              if s == V:
                  continue
              else:
                  Graph[s].append((t, d + h[s] - h[t]))
  
          ans = []
          # 各頂点からDijkstra O(VElogV)
          for i in range(V):
              d = Dijkstra(Graph, i)
              ans.append(d.shortest_distance())
  
          # 重みを元に戻す O(V^2)
          for i, line in enumerate(ans):
              h_i = h[i]
              for j, n in enumerate(line):
                  if n == float("inf"):
                      line[j] = "INF"
                  else:
                      line[j] -= h_i - h[j]
              tmp = " ".join(map(str, line))
              print(tmp)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: All Pairs Shortest Path
samples: [{"input": "4 6\n    0 1 1\n    0 2 5\n    1 2 2\n    1 3 4\n    2 3 1\n    3 2 7", "output": "0 1 3 4\n    INF 0 2 3\n    INF INF 0 1\n    INF INF 7 0"}, {"input": "4 6\n    0 1 1\n    0 2 -5\n    1 2 2\n    1 3 4\n    2 3 1\n    3 2 7", "output": "0 1 -5 -4\n    INF 0 2 3\n    INF INF 0 1\n    INF INF 7 0"}, {"input": "4 6\n    0 1 1\n    0 2 5\n    1 2 2\n    1 3 4\n    2 3 1\n    3 2 -7", "output": "NEGATIVE CYCLE"}]