#include <bits/stdc++.h>
using namespace std;
 
class Graph{
	public:
	int n, m;
	
	vector<vector<int>> adj;
	vector<vector<int>> W;
	vector<vector<int>> predecessor;
 
	Graph(int nodes): adj(nodes), W(nodes, vector<int>(nodes, INT_MAX)), 
						predecessor(nodes, vector<int>(nodes, -1)){
		n = nodes;
		m = 0;
		
		for(int i=0; i<n; ++i)
			W[i][i] = 0;
	}
 
	void addEdge(int u, int v, int weight){
		if(u >= n || v >=n || u < 0 || v < 0){ 
			cout<<"Either of the vertices doesn't exists in the graph.\n";
			return;
		}
 
		W[u][v] = weight;
		predecessor[u][v] = u;
 
		adj[u].push_back(v);
 
		++m;
	}
 
	void allPairsShortestPath(){
		
		for(int k = 0; k < n; ++k){
			for(int i = 0; i < n; ++i){
				for(int j = 0; j < n; ++j){
					if(W[i][k] != INT_MAX && W[k][j] != INT_MAX && W[i][k] + W[k][j] < W[i][j]){
						W[i][j] = W[i][k] + W[k][j];
						predecessor[i][j] = k;
					}
				}
			}
			
			// for(auto row: W){
			// 	cout<<"|\t";
			// 	for(auto col: row){
			// 		cout<<col<<"\t|\t";
			// 	}
			// 	cout<<"\n";
			// }
			// cout<<"-------------------------------\n";
		}
		
		cout<<"Final distance matrix(with rows/cols indexed [0-"<<n-1<<"]):\n";
		for(auto row: W){
			cout<<"|\t";
			for(auto col: row){
				cout<<col<<"\t|\t";
			}
			cout<<"\n";
		}
		
		cout<<"-------------------------------\n"
		"Predecessor matrix(with rows/cols indexed [0-"<<n-1<<"]):\n";
		for(auto row: predecessor){
			cout<<"|\t";
			for(auto col: row){
				cout<<col<<"\t|\t";
			}
			cout<<"\n";
		}	
 
		// cout<<"The shortest paths from given source "<<src<<" to\nall other nodes are,\n";
 
		// 	for(int u = 0; u < n; ++u){
		// 		if(u != src){
		// 			cout<<"----------------------------------------\n";
		// 			if(shortestPaths[u] < INT_MAX){
		// 				cout<<"Path length: "<<shortestPaths[u]<<" | Path: ";
		// 				printPath(predecessors, u);
		// 				cout<<"\n";
		// 			}
		// 			else{
		// 				cout<<"No path exits from given source "<<src<<" to "<<u<<"\n";
		// 			}
		// 		}
		// 	}
 
	}
 
	void printGraph(){ 
 
		if(!m){ 
			cout<<"The graph is empty!!\n";
			return;
		} 
 
		cout<<"Total # edges in the graph: "<<m<<"\n";
 
		for(int i = 0; i < n; ++i){ 
			cout<<"The edges from vertex "<<i<<":";
 
			for(auto val: adj[i])  
				cout<<"->"<<val;
 
			cout<<"\n"; 
		}
		cout<<"======================================================\n";
	}
 
	void printPath(vector<int> &predecessors, int par){
		if(par == -1)
			return;
 
		printPath(predecessors, predecessors[par]);
 
		cout<<(predecessors[par] == -1 ? "":"->")<<par;
	}
};
 
int main()
{
	int n, u, v, w; 
	cin>>n;
 
	Graph g(n);
 
	cin>>n;
 
	for(int i=0; i < n; ++i){
		cin>>u>>v>>w;
		g.addEdge(u,v,w);
	}
 
	g.printGraph();
 
	g.allPairsShortestPath();
 
	return 0;
}