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