I was running nodejs on port 80 a older version but still quite recent. and the usual sshd deamon on port 22. Even my password was pretty strong. How did they do this ? I am really surprised.
Anyway, before reinstalling you should definitely quarantine your box and figure out how they got in before reinstalling. Because if and when you don't know, and the specific vulnerability is inside the current version of your Linux distro the chance is almost 100% they will discover a fresh target once they scan for vulnerable servers and they will hack your box again.