That model, if I'm not mistaken, is still not on the Vintage list, so you SHOULD be able to call Apple and get a replacement set of media. Figure on ~$20US give or take. I would call immediately though, because very soon that unit will pass into vintage status, and that will limit your options somewhat.

Then I would suggest burning a copy (or three) of the replacement media they send you. And of course if you have a copy of 10.5, you can just install that. You don't need 10.4 to be installed first.