ddd

#include <bits/stdc++.h>
#define oo 1e9

using namespace std;

ifstream fin("roy-floyd.in");
ofstream fout("roy-floyd.out");

int a[105][105],n,m,cost;

int main()
{
    int i,k,j;
    fin>>n>>m;
    ///initializare matrice
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
            a[i][j]=a[j][i]=oo;
    ///citire arce
    for(k=1;k<=m;k++)
    {
        fin>>i>>j>>cost;
        a[i][j]=cost;
    }
    ///Roy-Floyd
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i!=j && i!=k && j!=k && a[i][j]>a[i][k]+a[k][j])
                    a[i][j]=a[i][k]+a[k][j];
    ///afisare
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            if(a[i][j]==oo) fout<<"-1 ";
            else fout<<a[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}