Boot into the installation media of the same distro being recovered.
Under Advanced Options, select the Rescue utility.
It will look like the installer is loading - select your language.
When you make it to the network configuration page, press the ESC key to drop back into the setup menu.
In the middle of the page, you should be able to select the Rescue/Recovery option.
Select your boot drive/partition as the root partition accordingly.
Drop into a shell on that partition.
You can now change the root password.