#include <fstream>
#include <iostream>
#include <stdio.h>
using namespace std;
int n,m;
int a[101][101],tr[101][101];
const int oo=1000000;
int main()
{
    ifstream fi("floyd.inp");
    ofstream fo("floyd.out");
    fi>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {a[i][j]=oo; tr[i][j]=j;}
     for(int i=1;i<=n;i++) a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        fi>>x>>y>>w;
        a[x][y]=w;
    }
    fo<<"D0"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(a[i][j]==oo) fo<<"oo "; else fo<<a[i][j]<<" ";
        fo<<endl;
    } fo<<endl;

    fo<<"P0"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(tr[i][j]==-1) fo<<"nil "; else fo<<tr[i][j]<<" ";
        fo<<endl;
    }
    fo<<"================"<<endl;


    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
           if(a[i][k]!=oo && a[k][j]!=oo && a[i][j]>a[i][k]+a[k][j])
           {
             a[i][j]=a[i][k]+a[k][j];
             tr[i][j]=tr[i][k];
           }


       fo<<"D"<<k<<endl;
       for(int i=1;i<=n;i++)
       {
        for(int j=1;j<=n;j++)
            if(a[i][j]==oo) fo<<"oo "; else fo<<a[i][j]<<" ";
        fo<<endl;
       } fo<<endl;

       fo<<"P"<<k<<endl;
       for(int i=1;i<=n;i++)
       {
        for(int j=1;j<=n;j++)
            if(tr[i][j]==-1) fo<<"nil "; else fo<<tr[i][j]<<" ";
        fo<<endl;
       }
       fo<<"================"<<endl;
    }

    for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
            if(i!=j)
         {
             int u=i,v=j;
           fo<<"Do dai tu "<<u<<" den "<<v<<":"<<a[u][v]<<endl;
           fo<<"  -Duong di: ";
           do
           {
                fo<<u<<"->";
                u=tr[u][v];
           } while (u!=v);
           fo<<u<<endl;

         }
    fi.close();
    fo.close();
}