Ultrafast dynamics of graphite is investigated by time-resolved photoemission spectroscopy. We observe spectral features of direct photoexcitations, non-thermal electron distributions, and recovery dynamics occurring with two time scales having distinct pump-power dependences. Additionally, we find an anomalous increase of the spectral intensity around the Fermi level, and we attribute this to spectral broadenings due to coupled optical phonons in the transient. The fingerprints of the coupled optical phonons occur from the temporal region where the electronic temperature is still not definable. This implies that there is a mechanism of ultrafast-and-efficient phonon generations beyond a two-temperature model.