It looks like you've got everything set up correctly. Once you've applied the "A" record (126.96.36.199), and CNAME (shops.myshopify.com) it typically takes up to 24 hours for those changes to apply. If 24 hours pass, and you're still unable to connect the domain, then you'll want to use free tools such as MXtoolbox to see if the records are appearing publicly.
If they aren't, then you'll want to reach out to your domain provider to troubleshoot the issue further as they'll be able to look into why the changes haven't applied. If they are appearing publicly, then it could be our system that is causing the issue. If you try to verify the domain three times, it should allow you to manually add the domain to your store. Once you have, the domain should work.
However; if you're still having issues with this, please let me know as I'd be happy to take a look!