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