#include<bits/stdc++.h>
using namespace std;
int f[50][50],n,u,v,w;
int main(){
	cin>>n;
	for(int i=0;i<50;++i){
		for(int j=0;j<50;++j) f[i][j]=1000;
	}
	for(int i=1;i<=n;++i){
		cin>>u>>v>>w;
		f[u][v]=w;
	}
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(f[i][j]>f[i][k]+f[k][j])
					f[i][j]=f[i][k]+f[k][j];
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j) cout<<f[i][j]<<" ";
		cout<<"\n";
	}
	cout<<f[1][6]<<endl;
	return 0;
}
/*
6
1 4 5
1 3 8
4 3 2
4 5 10
3 5 6
3 2 14
5 2 5
5 6 17
2 6 10
3 6 25
*/
//28