sub f{$_[$_[1]<$_[0]]}
 
@N=1..<>;
/ .* /,$_[$`][$&]=$_[$&][$`]=$' for@M=<>;
 
for$m(@N){
	for$x(@N){
		for$y(@N){
			if($x!=$y){
				$_[$x][$y]=f($_[$x][$y]||1e9,$_[$x][$m]+$_[$m][$y]);
			}
		}
	}
}
/ .* /,$\+=$_[$`][$&]<$' for@M;
 
print
