First and foremost, take your dog to the vet. If they have passed the shoe within 36 hours, there is a good chance that they did not ingest any of the shoe material. However, in the event that your dog has ingested any shoe material, the doctor will be able to evaluate the situation and advise you on what to do next.
In some cases, dogs may vomit or have diarrhea after eating shoes. If this is the case, you may want to feed them a bland diet for a few days in order to help limit their exposure to potential toxins. In addition, you might want to keep an eye on their hydration levels and give them plenty of fresh water.