using System;
using System.Collections.Generic;
using System.Linq;
// Q047 全点対間最短経路 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 6");
WillReturn.Add("0 1 1");
WillReturn.Add("0 2 5");
WillReturn.Add("1 2 2");
WillReturn.Add("1 3 4");
WillReturn.Add("2 3 1");
WillReturn.Add("3 2 7");
//0 1 3 4
//INF 0 2 3
//INF INF 0 1
//INF INF 7 0
}
else if (InputPattern == "Input2") {
WillReturn.Add("4 6");
WillReturn.Add("0 1 1");
WillReturn.Add("0 2 -5");
WillReturn.Add("1 2 2");
WillReturn.Add("1 3 4");
WillReturn.Add("2 3 1");
WillReturn.Add("3 2 7");
//0 1 -5 -4
//INF 0 2 3
//INF INF 0 1
//INF INF 7 0
}
else if (InputPattern == "Input3") {
WillReturn.Add("4 6");
WillReturn.Add("0 1 1");
WillReturn.Add("0 2 5");
WillReturn.Add("1 2 2");
WillReturn.Add("1 3 4");
WillReturn.Add("2 3 1");
WillReturn.Add("3 2 -7");
//NEGATIVE CYCLE
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();
SplitAct(InputList[0]);
int V = wkArr[0];
int UB = V - 1;
int[,] KyoriArr = new int[UB + 1, UB + 1];
const int INFTY = int.MaxValue;
// 初期化処理
for (int I = 0; I <= UB; I++) {
for (int J = 0; J <= UB; J++) {
KyoriArr[I, J] = (I == J) ? 0 : INFTY;
}
}
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
KyoriArr[wkArr[0], wkArr[1]] = wkArr[2];
}
// ワーシャルフロイド法
for (int K = 0; K <= UB; K++) {
for (int I = 0; I <= UB; I++) {
if (KyoriArr[I, K] == INFTY) continue;
for (int J = 0; J <= UB; J++) {
if (KyoriArr[K, J] == INFTY) continue;
int CurrKouho = KyoriArr[I, K] + KyoriArr[K, J];
if (KyoriArr[I, J] > CurrKouho) {
KyoriArr[I, J] = CurrKouho;
}
}
}
}
// 負の閉路のチェック
bool HasNegativeCycle = false;
for (int I = 0; I <= UB; I++) {
if (KyoriArr[I, I] < 0) HasNegativeCycle = true;
}
if (HasNegativeCycle) {
Console.WriteLine("NEGATIVE CYCLE");
return;
}
for (int I = 0; I <= UB; I++) {
for (int J = 0; J <= UB; J++) {
if (KyoriArr[I, J] == INFTY) {
Console.Write("INF");
}
else {
Console.Write(KyoriArr[I, J]);
}
if (J < UB) Console.Write(" ");
}
Console.WriteLine();
}
}
}