From my old Unix days which was a while ago we just booted into single
user and changed the password.

Now in Ubuntu I think you can run "sudo passwd root" and then it will
ask you for your password which will give it permission to change it.

Now the disclaimer I am still learning this system so I may be all wet.
But I am willing to learn.