#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>
using namespace std;
void citire(int &n,int a[][100])
{
int m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=50000;
for(int i=1;i<=m;i++)
{
int x,y,nr;
cin>>x>>y>>nr;
a[x][y]=nr;
}
}
void afisare(int n,int a[][100])
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(a[i][j]!=50000)
cout<<setw(3)<<a[i][j];
else cout<<setw(3)<<"--";
cout<<endl;
}
}
void Roy_Floyd(int n,int a[][100])
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
{
///a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
}
}
int main()
{
int n,a[100][100];
citire(n,a);
Roy_Floyd(n,a);
afisare(n,a);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBjaXRpcmUoaW50ICZuLGludCBhW11bMTAwXSkKewogICAgaW50IG07CiAgICBjaW4+Pm4+Pm07CiAgICBmb3IoaW50IGk9MTtpPD1uO2krKykKICAgICAgICBmb3IoaW50IGo9MTtqPD1uO2orKykKICAgICAgICBhW2ldW2pdPTUwMDAwOwogICAgZm9yKGludCBpPTE7aTw9bTtpKyspCiAgICB7CiAgICAgICAgaW50IHgseSxucjsKICAgICAgICBjaW4+Png+Pnk+Pm5yOwogICAgICAgIGFbeF1beV09bnI7CiAgICB9Cn0Kdm9pZCBhZmlzYXJlKGludCBuLGludCBhW11bMTAwXSkKewogICAgZm9yKGludCBpPTE7aTw9bjtpKyspewogICAgICAgIGZvcihpbnQgaj0xO2o8PW47aisrKQogICAgICAgICAgICBpZihhW2ldW2pdIT01MDAwMCkKICAgICAgICAgICAgY291dDw8c2V0dygzKTw8YVtpXVtqXTsKICAgICAgICAgICAgZWxzZSBjb3V0PDxzZXR3KDMpPDwiLS0iOwogICAgICAgICAgICBjb3V0PDxlbmRsOwogICAgfQp9CnZvaWQgUm95X0Zsb3lkKGludCBuLGludCBhW11bMTAwXSkKewogICAgZm9yKGludCBrPTE7azw9bjtrKyspCiAgICAgICAgZm9yKGludCBpPTE7aTw9bjtpKyspCiAgICAgICAgICAgIGZvcihpbnQgaj0xO2o8PW47aisrKQogICAgICAgICAgICAgICAgaWYoaSE9aikKICAgIHsKICAgICAgICAvLy9hW2ldW2pdPW1pbihhW2ldW2pdLGFbaV1ba10rYVtrXVtqXSk7CiAgICAgICAgaWYoYVtpXVtqXT5hW2ldW2tdK2Fba11bal0pCiAgICAgICAgICAgIGFbaV1bal09YVtpXVtrXSthW2tdW2pdOwogICAgfQp9CmludCBtYWluKCkKewogICAgaW50IG4sYVsxMDBdWzEwMF07CiAgICBjaXRpcmUobixhKTsKICAgIFJveV9GbG95ZChuLGEpOwogICAgYWZpc2FyZShuLGEpOwogICAgcmV0dXJuIDA7Cn0KIA==