// Algorytm Floyda-Warshalla
// Data: 20.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program floyd_warshall;

// Typ danych
// dla macierzy dynamicznej
type
  nptr = array of integer;

var
  // Macierz minimalnych
  // kosztów dojścia
  d : array of nptr;
  i,j,k,n,m,x,y,w : integer;
begin
  // Czytamy liczbę
  // wierzchołków oraz krawędzi
  read(n, m);
  // Tworzymy dynamiczną
  // macierz d
  SetLength(d, n);
  for i := 0 to n-1 do
  begin
    // Tworzymy wiersz macierzy
    SetLength(d[i], n);
    for j := 0 to n-1 do
      // Wiersz wypełniamy
      // największą liczbą
      // dodatnią
      d[i][j] := MAXINT;
    // Jednakże na przekątnej
    // wpisujemy 0
    d[i][i] := 0;
  end;
  for i := 1 to m do
  begin
    // Czytamy definicję krawędzi
    read(x, y, w);
    // Wagę krawędzi
    // umieszczamy w macierzy d
    d[x][y] := w;
  end;
  // Algorytm Floyda-Warshalla
  for k := 0 to n-1 do
    for i := 0 to n-1 do
      for j := 0 to n-1 do
      begin
        if (d[i][k] = MAXINT) or
           (d[k][j] = MAXINT) then
          continue;
        w := d[i][k]+d[k][j];
        if d[i][j] > w then
          d[i][j] := w;
      end;
  // Wyświetlamy wyniki
  writeln;
  for i := 0 to n-1 do
    for j := 0 to n-1 do
    begin
      write('d[',i,',',j,'] = ');
      if d[i][j] = MAXINT then
        writeln('NO PATH')
      else
        writeln(d[i][j]);
    end;
  // Usuwamy macierz dynamiczną
  for i := 0 to n-1 do
    SetLength(d[i], 0);
  SetLength(d, 0);
end.

// Algorytm Floyda-Warshalla
// Data: 20.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// "plus nieskończoność"
const int MAXINT = 2147483647;

int main()
{
  // Macierz minimalnych
  // kosztów dojścia
  int ** d;
  int i,j,k,n,m,x,y,w;

  // Czytamy liczbę
  // wierzchołków oraz krawędzi
  cin >> n >> m;
  // Tworzymy dynamiczną
  // macierz d
  d = new int * [n];
  for(i = 0; i < n; i++)
  {
    // Tworzymy wiersz macierzy
    d[i] = new int [n];
    for(j = 0; j < n; j++)
      // Wiersz wypełniamy
      // największą liczbą
      // dodatnią
      d[i][j] = MAXINT;
    // Jednakże na przekątnej
    // wpisujemy 0
    d[i][i] = 0;
  }
  for(i = 0; i < m; i++)
  {
    // Czytamy
    // definicję krawędzi
    cin >> x >> y >> w;
    // Wagę krawędzi
    // umieszczamy w macierzy d
    d[x][y] = w;
  }
  // Algorytm Floyda-Warshalla
  for(k = 0; k < n; k++)
    for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
      {
        if((d[i][k] == MAXINT) ||
           (d[k][j] == MAXINT))
          continue;
        w = d[i][k]+d[k][j];
        if(d[i][j] > w)
          d[i][j] = w;
      }
  // Wyświetlamy wyniki
  cout << endl;
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
    {
      cout << "d[" << i
           << "," << j
           << "] = ";
      if(d[i][j] == MAXINT)
        cout << "NO PATH";
      else
        cout << d[i][j];
      cout << endl;
    }
  // Usuwamy macierz dynamiczną
  for(i = 0; i < n; i++)
    delete [] d[i];
  delete [] d;
  return 0;
}

' Algorytm Floyda-Warshalla
' Data: 20.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' "plus nieskończoność"
const MAXINT = 2147483647

' Macierz minimalnych
' kosztów dojścia
Dim As Integer Ptr Ptr d
Dim As Integer i,j,k,n,m,x,y,w

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków
' oraz krawędzi
Input #1, n, m
' Tworzymy
' dynamiczną
' macierz d
d = New Integer Ptr [n]
For i = 0 To n-1
  ' Tworzymy
  ' wiersz macierzy
  d[i] = New Integer [n]
  For j = 0 To n-1
    ' Wiersz wypełniamy
    ' największą liczbą
    ' dodatnią
    d[i][j] = MAXINT
  Next
  ' Jednakże na przekątnej
  ' wpisujemy 0
  d[i][i] = 0
Next
For i = 1 To m
  ' Czytamy definicję krawędzi
  Input #1, x, y, w
  ' Wagę krawędzi
  ' umieszczamy
  ' w macierzy d
  d[x][y] = w
Next
Close #1
' Algorytm Floyda-Warshalla
For k = 0 To n-1
  For i = 0 To n-1
    For j = 0 To n-1
      If (d[i][k] = MAXINT) OrElse _
         (d[k][j] = MAXINT) Then _
        Continue For
      w = d[i][k]+d[k][j]
      If d[i][j] > w Then _
        d[i][j] = w
    Next
  Next
Next 
' Wyświetlamy wyniki
Print
For i = 0 To n-1
  For j = 0 To n-1
    Print Using "d[&,&] =";i;j;
    If d[i][j] = MAXINT Then
      Print " NO PATH"
    Else
      Print d[i][j]
    End If
  Next
Next
' Usuwamy macierz dynamiczną
For i = 0 To n-1
  Delete [] d[i]
Next
Delete [] d
End

# Algorytm Floyda-Warshalla
# Data: 17.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# "plus nieskończoność"
MAXINT = 2147483647
# Czytamy liczbę
# wierzchołków
# oraz krawędzi
z = input().split()
n = int(z[0])
m = int(z[1])
# Tworzymy
# dynamiczną
# macierz d
d = [None] * n
for i in range(n):
    # Tworzymy
    # wiersz macierzy
    d[i] = [MAXINT] * n
    # Na przekątnej
    # wpisujemy 0
    d[i][i] = 0
for i in range(m):
    # Czytamy definicję krawędzi
    z = input().split()
    x = int(z[0])
    y = int(z[1])
    w = int(z[2])
    # Wagę krawędzi
    # umieszczamy
    # w macierzy d
    d[x][y] = w
# Algorytm Floyda-Warshalla
for k in range(n):
    for i in range(n):
        for j in range(n):
            if (d[i][k] == MAXINT) or \
               (d[k][j] == MAXINT):
                continue
            w = d[i][k]+d[k][j]
            if d[i][j] > w:
                d[i][j] = w
# Wyświetlamy wyniki
print()
for i in range(n):
    for j in range(n):
        print("d[",i,",",j,"] = ",
               sep="",end="")
        if d[i][j] == MAXINT:
            print("NO PATH")
        else:
            print(d[i][j])
# Usuwamy macierz dynamiczną
for i in range(n):
    d[i] = None
del d

// Algorytm Floyda-Warshalla
// Data: 21.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program floyd_warshall2;

// Typ danych dla
// macierzy dynamicznej
type
  nptr = array of integer;

// Zmienne globalne
var
  // Macierze kosztów
  // oraz poprzedników
  d, p : array of nptr;
  // Liczba wierzchołków
  // i krawędzi
  n, m : integer;

// Funkcja wyznaczania
// kosztów dojścia oraz
// minimalnych ścieżek
// w grafie ważonym
//---------------------
function FloydWarshall : boolean;
var
  i, j, k, w : integer;

begin
  for k := 0 to n-1 do
    for i := 0 to n-1 do
      for j := 0 to n-1 do
      begin
        if (d[i][k] = MAXINT) or
           (d[k][j] = MAXINT) then
          continue;
        w := d[i][k] + d[k][j];
        if d[i][j] > w then
        begin
          d[i][j] := w;
          p[i][j] := p[k][j];
        end;
      end;
  for i := 0 to n-1 do
    if d[i][i] < 0 then
      // Ujemny cykl
      Exit(false);
  FloydWarshall := true;
end;

// Rekurencyjna procedura
// odtwarzania minimalnej
// ścieżki z macierzy
// poprzedników p
//-----------------------
procedure FWPath(i, j : integer);
begin
  if i = j then
    write(i, ' ')
  else if p[i][j] = -1 then
    write('NO PATH')
  else
  begin
    FWPath(i, p[i][j]);
    write (j, ' ');
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
var
  i, j, x, y, w : integer;
begin
  // Czytamy liczbę
  // wierzchołków oraz
  // krawędzi
  read(n, m);
  // Tworzymy dynamiczną
  // macierz d
  SetLength(d, n);
  // Tworzymy dynamiczną
  // macierz p
  SetLength(p, n);
  for i := 0 to n-1 do
  begin
    // Tworzymy wiersz
    // macierzy d
    SetLength(d[i], n);
    // Tworzymy wiersz
    // macierzy p
    SetLength(p[i], n);
    for j := 0 to n-1 do
    begin
      // Wiersz d wypełniamy
      // największą liczbą
      // dodatnią
      d[i][j] := MAXINT;
      // Wiersz p wypełniamy
      // liczbami -1
      // (brak poprzednika)
      p[i][j] := -1;
    end;
    // Jednakże na przekątnej d
    // wpisujemy 0
    d[i][i] := 0;
  end;
  for i := 1 to m do
  begin
    // Czytamy definicję
    // krawędzi
    read(x, y, w);
    // Wagę krawędzi
    // umieszczamy
    // w macierzy d
    d[x][y] := w;
    // Poprzednikiem y jest x
    p[x][y] := x;
  end;
  // Wywołujemy funkcję
  // Floyda-Warshalla
  writeln;
  if FloydWarshall then
  begin
    // Wyświetlamy wyniki
    for i := 0 to n-1 do
      for j := 0 to n-1 do
      begin
        write(i, '-', j, ' : ');
        FWPath(i, j);
        if d[i][j] < MAXINT then
          write('$', d[i][j]);
        writeln;
      end;
  end
  else
    writeln('Negative cycle found');
  writeln;
  // Usuwamy macierze dynamiczne
  for i := 0 to n-1 do
  begin
    SetLength(d[i], 0);
    SetLength(p[i], 0);
  end;
  SetLength(d, 0);
  SetLength(p, 0);
end.

// Algorytm Floyda-Warshalla
// Data: 21.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// "plus nieskończoność"
const int MAXINT = 2147483647;

// Zmienne globalne
//-----------------
// Macierze kosztów
// oraz poprzedników
int **d, **p;
// Liczba wierzchołków
// i krawędzi
int n, m;

// Funkcja wyznaczania
// kosztów dojścia oraz
// minimalnych ścieżek
// w grafie ważonym
//---------------------
bool FloydWarshall()
{
  int i, j, k, w;

  for(k = 0; k < n; k++)
    for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
      {
        if((d[i][k] == MAXINT) ||
           (d[k][j] == MAXINT))
          continue;
        w = d[i][k]+d[k][j];
        if(d[i][j] > w)
        {
          d[i][j] = w;
          p[i][j] = p[k][j];
        }
      }
  for(i = 0; i < n; i++)
    if(d[i][i] < 0) return
      // Ujemny cykl
      false;
  return true;
}

// Rekurencyjna procedura
// odtwarzania minimalnej
// ścieżki z macierzy
// poprzedników p
//-----------------------
void FWPath(int i, int j)
{
  if(i == j)
    cout << i << " ";
  else if(p[i][j] == -1)
    cout << "NO PATH";
  else
  {
    FWPath (i, p [i][j]);
    cout << j << " ";
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
int main()
{
  int i, j, x, y, w;

  // Czytamy liczbę
  // wierzchołków oraz
  // krawędzi
  cin >> n >> m;
  // Tworzymy dynamiczną
  // macierz d
  d = new int * [n];
  // Tworzymy dynamiczną
  // macierz p
  p = new int * [n];

  for(i = 0; i < n; i++)
  {
    // Tworzymy wiersz
    // macierzy d
    d[i] = new int [n];
    // Tworzymy wiersz
    // macierzy p
    p[i] = new int [n];
    for(j = 0; j < n; j++)
    {
      // Wiersz d wypełniamy
      // największą liczbą
      // dodatnią
      d[i][j] = MAXINT;
      // Wiersz p wypełniamy
      // liczbami -1
      // (brak poprzednika)
      p[i][j] = -1;
    }
    // Jednakże na przekątnej d
    // wpisujemy 0
    d[i][i] = 0;
  }
  for(i = 0; i < m; i++)
  {
    // Czytamy definicję krawędzi
    cin >> x >> y >> w;
    // Wagę krawędzi umieszczamy
    // w macierzy d
    d[x][y] = w;
    // Poprzednikiem y jest x
    p[x][y] = x;
  }
  // Wywołujemy procedurę
  // Floyda-Warshalla
  cout << endl;
  if(FloydWarshall())
  {
    // Wyświetlamy wyniki
    for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
      {
        cout << i << "-"
             << j << ": ";
        FWPath(i, j);
        if(d[i][j] < MAXINT)
          cout << "$" << d[i][j];
        cout << endl;
      }
  }
  else
    cout << "Negative cycle found"
         << endl;
  cout << endl;
  // Usuwamy macierze dynamiczne
  for(i = 0; i < n; i++)
  {
    delete [] d[i];
    delete [] p[i];
  }
  delete [] d;
  delete [] p;
  return 0;
}

' Algorytm Floyda-Warshalla
' Data: 21.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' "plus nieskończoność"
const MAXINT = 2147483647

' Zmienne globalne
'-----------------
' Macierze kosztów oraz poprzedników
Dim Shared As Integer Ptr Ptr d, p
' Liczba wierzchołków i krawędzi
Dim Shared As Integer n, m

' Funkcja wyznaczania
' kosztów dojścia oraz
' minimalnych ścieżek
' w grafie ważonym
'---------------------
Function FloydWarshall As Integer
  Dim As Integer i, j, k, w
  For k = 0 To n-1
    For i = 0 To n-1
      For j = 0 To n-1
        if (d[i][k] = MAXINT) OrElse _
           (d[k][j] = MAXINT) Then _
          Continue For
        w = d[i][k]+d[k][j]
        If d[i][j] > w Then
          d[i][j] = w
          p[i][j] = p[k][j]
        End If
      Next
    Next
  Next
  For i = 0 To n-1
    If d[i][i] < 0 Then
      ' Ujemny cykl
      Return 0
    End If
  Next
  Return 1
End Function

' Rekurencyjna procedura
' odtwarzania minimalnej
' ścieżki z macierzy
' poprzedników p
'----------------------
Sub FWPath(ByVal i As Integer, _
           ByVal j As Integer)
  If i = j Then
  	 Print i;
  ElseIf p[i][j] = -1 Then
    Print " NO PATH";
  Else
    FWPath(i, p[i][j])
    Print j;
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, j, x, y, w

Open Cons For Input As #1
' Czytamy liczbę wierzchołków
' oraz krawędzi
Input #1, n, m
' Tworzymy dynamiczną
' macierz d
d = New Integer Ptr [n]
' Tworzymy dynamiczną
' macierz p
p = New Integer Ptr [n]
For i = 0 To n-1
  ' Tworzymy wiersz
  ' macierzy d
  d[i] = New Integer [n]
  ' Tworzymy wiersz
  ' macierzy p
  p[i] = New Integer [n]
  For j = 0 To n-1
    ' Wiersz d wypełniamy
    ' największą liczbą
    ' dodatnią
    d[i][j] = MAXINT
    ' Wiersz p wypełniamy
    ' liczbami -1
    ' (brak poprzednika)
    p[i][j] = -1
  Next
  d[i][i] = 0
Next
For i = 1 To m
  ' Czytamy definicję krawędzi
  Input #1, x, y, w
  ' Wagę krawędzi umieszczamy
  ' w macierzy d
  d[x][y] = w
  ' Poprzednikiem y jest x
  p[x][y] = x
Next
' Wywołujemy funkcję
' Floyda-Warshalla
Print
If FloydWarshall() = 1 Then
  ' Wyświetlamy wyniki
  For i = 0 To n-1
    For j = 0 To n-1
      Print Using "&-&:";i;j;
      FWPath(i, j)
      If d[i][j] < MAXINT Then _
        Print Using " $&";d[i][j];
      Print
    Next
  Next
Else
  Print "Negative cycle found"
End If
Print
' Usuwamy macierze dynamiczne
for i = 0 To n-1
  Delete [] d[i]
  Delete [] p[i]
Next
Delete [] d
Delete [] p
End

# Algorytm Floyda-Warshalla
# Data: 19.02.2025
# (C)2014 mgr Jerzy Wałaszek
#---------------------------

# "plus nieskończoność"
MAXINT = 2147483647

# Funkcja wyznaczania
# kosztów dojścia oraz
# minimalnych ścieżek
# w grafie ważonym
#---------------------
def floyd_warshall():
    global n,d,p
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (d[i][k] == MAXINT) or \
                     (d[k][j] == MAXINT):
                    continue
                w = d[i][k]+d[k][j]
                if d[i][j] > w:
                    d[i][j] = w
                    p[i][j] = p[k][j]
    for i in range(n):
        if d[i][i] < 0:
            # Ujemny cykl
            return False
    return True


# Rekurencyjna procedura
# odtwarzania minimalnej
# ścieżki z macierzy
# poprzedników p
#----------------------
def fw_path(i, j):
    global p
    if i == j:
        print(i, end=" ")
    elif p[i][j] == -1:
        print(" NO PATH", end=" ")
    else:
        fw_path(i, p[i][j])
        print(j, end=" ")


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków
# oraz krawędzi
z = input().split()
n = int(z[0])
m = int(z[1])
# Tworzymy dynamiczną
# macierz d
d = [None] * n
# Tworzymy dynamiczną
# macierz p
p = [None] * n
for i in range(n):
    # Tworzymy wiersz
    # macierzy d
    d[i] = [MAXINT] * n
    # Tworzymy wiersz
    # macierzy p
    p[i] = [-1] * n
    d[i][i] = 0
for i in range(m):
    # Czytamy definicję krawędzi
    z = input().split()
    x = int(z[0])
    y = int(z[1])
    w = int(z[2])
    # Wagę krawędzi umieszczamy
    # w macierzy d
    d[x][y] = w
    # Poprzednikiem y jest x
    p[x][y] = x
# Wywołujemy funkcję
# Floyda-Warshalla
print()
if floyd_warshall():
    # Wyświetlamy wyniki
    for i in range(n):
        for j in range(n):
            print(i,"-",j,sep="",end=" ")
            fw_path(i, j)
            if d[i][j] < MAXINT:
                print(" $",d[i][j],sep="",end=" ")
            print()
else:
    print("Negative cycle found")
print()
# Usuwamy macierze dynamiczne
for i in range(n):
    d[i] = None
    p[i] = None
del d,p