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: V, E = map(int, input().split())
  cost_matrix = [[float("inf")] * V for _ in range(V)]
  for i in range(V):
      cost_matrix[i][i] = 0
  for i in range(E):
      start, end, cost = map(int, input().split())
      cost_matrix[start][end] = cost
  for stop in range(V):
      for start in range(V):
          for end in range(V):
              cost_matrix[start][end] = min(
                  cost_matrix[start][end],
                  cost_matrix[start][stop] + cost_matrix[stop][end],
              )
  is_negative = False
  for start in range(V):
      for end in range(V):
          if cost_matrix[start][end] < 0 and start == end:
              is_negative = True
          elif cost_matrix[start][end] == float("inf"):
              cost_matrix[start][end] = "INF"
  if is_negative:
      print("NEGATIVE CYCLE")
  else:
      for start in range(V):
          res = list(map(str, cost_matrix[start]))
          print(" ".join(res))
  
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"}]