How to recover the root password on ubuntu server

I lost my root/super user password on Ubuntu server.
I tried to boot in a recovery mode and select option drop to root shell.

But it is always asks for:

Give root password for maintenance (or type Control-D to continue)

and I don't remember it.

Try Control-D when it prompts you for the root password. If that doesn't work, then try this:

http://www.howtogeek.com/howto/linux/reset-your-forgotten-ubuntu-password-in-2-minutes-or-less/

Then scroll down to "Alternate Root Shell Method".