You've gotta find your way to Nikeah. From South Figaro, head back through the cave and north to Narshe. Hopefully, the path'll be cleared, because Nikeah lies to the southeast from there.

Once you're there, you've gotta make your way east. Eventually, you'll end up in familiar territory (the old man's house, the Phantom Forest). Then, just head back to the Veldt like you did before in Sabin's scenario.