Get a little bit of the toothpaste out of the scrubber. I didn't do this part when I dealt with the other shoe and it foamed up and soaked in. I had to spend a while getting it all out. There's probably some still in there.
These shoes had quite a bit of dirt and dust in them. If yours are old and dirty, this step will benefit them. If they're new and you want to preserve the colour, ignore this. It might make them look faded.