Making this a non-event next time
Save the backup codes where you will find them
A password manager, not a screenshot. You will not remember where the screenshot went.
Use an authenticator that syncs
Apps like 1Password, Authy, and iCloud Passwords restore onto a new phone. Device-bound apps do not.
Keep one remembered browser
A personal machine with Remember this device selected is a second way in. Never do this on a shared or public computer.
Review approved devices occasionally
Settings lists the browsers currently remembered for 2FA. Sign out any you do not recognise.