As Robert mentioned, just replace the heatsink paste. Remember to use only a dab of it, not too much or little. Be sure the cpu fan is 100% running. When heat was present from before it could have stressed the componets, and its important to understand it is now maybe too late, the weak link is stressing out and causes a shutdown for whatever reason. If not the cpu, then psu comes into play. Leave the side cover off and see what happens after paste is replaced. AND if you haven't already clean the dust bunnies out.
"The only reason I don't think it's an overheating problem is, it shuts down right when I start my computer. Yesterday, I pushed the power button and it shut down in a second or two. And this happens after the computer has been off for the whole day, so it couldn't be hot anymore."
As I explained above, the weak link is already affected, so heat damage maybe present. In other words don't take anything for granted. Also, check the bios "over temp" setting, it can be set to reboot or shutdown, what are the results if you reset that?