$M=<>-1;@@=map/ (.*) /?$%{$1}{$`}=$%{$`}{$1}=$':$_,<>;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