#include<bits/stdc++.h>
using namespace std;
 
 
int main()
{
    int n, e;
    cin>>n>>e;
    long long int graph[n+1][n+1];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)graph[i][j] = 0;
            else graph[i][j] = INT_MAX;
        }
    }
 
    int u, v, w;
    for(int i = 1; i <= e; i++)
    {
        cin>>u>>v>>w;
        graph[u][v] = w;
    }
    cout<<"A0"<<endl;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cout<<graph[i][j]<<" ";
        }
        cout<<endl;
    }
 
 
 
    for(int k = 1; k <= n; k++)
    {
        cout<<"A"<<k<<endl;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                //if(i == 1&&k==1)cout<<graph[i][j]<<" "<<graph[i][k]+graph[k][j]<<endl;
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
 
            }
 
        }
        for(int p = 1; p <= n; p++)
        {
            for(int q = 1; q <= n; q++)
            {
                cout<<graph[p][q]<<" ";
            }
            cout<<endl;
        }
    }
 
 
 
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgppbnQgbWFpbigpCnsKICAgIGludCBuLCBlOwogICAgY2luPj5uPj5lOwogICAgbG9uZyBsb25nIGludCBncmFwaFtuKzFdW24rMV07CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICBmb3IoaW50IGogPSAxOyBqIDw9IG47IGorKykKICAgICAgICB7CiAgICAgICAgICAgIGlmKGkgPT0gailncmFwaFtpXVtqXSA9IDA7CiAgICAgICAgICAgIGVsc2UgZ3JhcGhbaV1bal0gPSBJTlRfTUFYOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgdSwgdiwgdzsKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gZTsgaSsrKQogICAgewogICAgICAgIGNpbj4+dT4+dj4+dzsKICAgICAgICBncmFwaFt1XVt2XSA9IHc7CiAgICB9CiAgICBjb3V0PDwiQTAiPDxlbmRsOwogICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICB7CiAgICAgICAgZm9yKGludCBqID0gMTsgaiA8PSBuOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBjb3V0PDxncmFwaFtpXVtqXTw8IiAiOwogICAgICAgIH0KICAgICAgICBjb3V0PDxlbmRsOwogICAgfQoKCgogICAgZm9yKGludCBrID0gMTsgayA8PSBuOyBrKyspCiAgICB7CiAgICAgICAgY291dDw8IkEiPDxrPDxlbmRsOwogICAgICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGludCBqID0gMTsgaiA8PSBuOyBqKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIC8vaWYoaSA9PSAxJiZrPT0xKWNvdXQ8PGdyYXBoW2ldW2pdPDwiICI8PGdyYXBoW2ldW2tdK2dyYXBoW2tdW2pdPDxlbmRsOwogICAgICAgICAgICAgICAgZ3JhcGhbaV1bal0gPSBtaW4oZ3JhcGhbaV1bal0sIGdyYXBoW2ldW2tdK2dyYXBoW2tdW2pdKTsKCiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICAgICAgIGZvcihpbnQgcCA9IDE7IHAgPD0gbjsgcCsrKQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGludCBxID0gMTsgcSA8PSBuOyBxKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNvdXQ8PGdyYXBoW3BdW3FdPDwiICI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgY291dDw8ZW5kbDsKICAgICAgICB9CiAgICB9CgoKCn0K

NCA3ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMSAyIDMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMiAxIDggICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMiAzIDIgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMSA0IDcgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgNCAxIDIgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMyAxIDUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMyA0IDEg

4 7                                                                              1 2 3                                                                            2 1 8                                                                            2 3 2                                                                            1 4 7                                                                            4 1 2                                                                            3 1 5                                                                            3 4 1