Assuming you did wait for Shadow on the Floating Continent, you will find him, as well as the weapon you will need to bet in the Coloseum, in the cave of the Veltd.

If you didn't wait for him, you are terribly out of luck. You will still find the weapon, but Shadow is gone forever. Instead, you'll find Relm in the cave.