their punishment should be to have huge billboards in their hometowns with their mugshots and the text "This man hates your dog! He murdered a puppy!"

Then wait and see what the locals do to him.