$N=<>-1;
@S=map/ .* /?$%[$&][$`]=$%[$`][$&]=$':$_,<>;
for$k(@T=0..$N){
	for$i(@T){
		$%[$i][$_]-=$-=($%[$i][$_]||=$\=9e9)-$%[$k][$i]-$%[$k][$_]for@T
	}
}
//,map$'-$_&&($\-=$-=$\-$S[$']-$S[$_]-$%[0][$']-$%[$'][$_]-$%[$_][$N]),@@for@@=1..$N-1;
print