Ok, Here's the update, I got the thermal paste first thing today and opened up the panel, took the fan and the sink apart and applied a thin coat as was directed on the tube, assembled everything back, started the pc and my readings were :
1. CPU = 19 (at Idle) went to 45-46 (after gaming)
2. Core 0 = 38 "" 60-61 ""
3. Core 1 = 38 "" 60-61 ""
I am really amazed to see these results, I doubted that the paste would make this much difference.
I am really thankful to all for helping me and I think these temp are Ok now?