When you softmod it, there are no dependencies on the sd card to load "other software". The "other software", usb config loader,wiiflow etc, can be on an sd card or fat32 HDD. You only need the sd card for the initial installation.
Just download the apps again. You can use modmii to download.
As you were not using a HDD, would I be correct in assuming you were using DVDs?