Don't see a reason for the overheating unless you were applying more than 5V for power or to any of the inputs, or had any of the outputs grounded or going to 5V.
An exact schematic of all the gate connections (including unused gates, and power and ground) would help, as we seem to be missing...