Well if it's not on the shore, your best bet is to take the Highwind and scout out the area. That or just wait a good few minutes for Weapon to make its way to Midgar.