#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main(){
    int V,e;
    cin>>v>>e;
    vector<vector<int>> graph(V,vector<int>(V,INF));
    for(int i=0;i<V;i++) graph[i][i]=0;
    for(int i=0;i<e;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(w<graph[u][v]){
            graph[u][v]=w;
            graph[v][u]=w;
        }
    }
    vector<vector<int>> original = graph;
    cout<<"Original Matrix \n";
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            if(original[i][j]==INF) cout<<"INF"<<endl;
            else cout<<original[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int k=0;k<V;k++){
        for(int i=0;i<V;i++){
            for(int j=0;j<V;j++){
                if(graph[i][k]<INF && graph[k][j]<INF){
                    graph[i][j] = min({graph[i][j],graph[i][k]+graph[k][j]});
                }
            }
        }
    }
    cout<<"Shortest Path."<<endl;
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            if(graph[i][j]==INF) cout<<"INF"<<endl;
            else cout<<graph[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}