Cpu Temps too high?

Solution
It is worth noting that because laptops are smaller than desktops, they do not have room for powerful cooling systems. I would consider your temperatures to probably be normal.
73C is not dangerously high... What are your core temperatures?

I would still attempt to clean out the dust and apply new thermal paste.

Please refer to your laptop manual for instructions on disassembly. Laptops can be tricky... If you just do what looks right, then you may end up bending or breaking something.