Making use of the Sagdeev pseudo-potential approach, we derive the energy like equation for dust-acoustic (DA) solitary waves in a complex plasma having negatively charged cold dust, and electrons/ions featuring the Tsallis distribution. The effects of electron and ion nonextensivity on the DA soliton profile are examined. It is shown that depending on the strength of particle nonextensivity, our plasma model may admit compressive as well as rarefactive DA solitary waves. Our results complement previously published results on this problem.