but it got severly hot after a few minutes
It probably won't reach on its own, so you`ll need to run jumper wires from the relevant sockets on the Arduino to the LM35 pins.
I'd like to make my jumpers a little more robust by adding proper pins to the ends. Does anyone have a cheap source of pins and a crimp tool?
I use pre made up jumper wires, similar to these: