my @list; # Komibantionen ['start','ziel']
foreach my $start (keys %entfernung) {
    foreach my $ziel (keys %{$entfernung{$start}}) {
        push @list, [$start,$ziel,$entfernung{$start}{$ziel}];
    }
}

my @sorted_list = sort { $a->[2] <=> $b->[2] } @list;
printf "Von %s nach %s: %d\n", @$_ foreach @sorted_list;