On-board battery consumption, cellular disconnectivity, and frequent handoff are key challenges for unmanned aerial vehicle (UAV) based delivery missions, a.k.a., cargo-UAV. Indeed, with the introduction of UAV technology into cargo shipping and logistics, designing energy-efficient paths becomes a serious issue for the next retail industry transformation. Typically, the latter has to guarantee uninterrupted or slightly interrupted cellular connectivity for the UAV's command and control through a small number of handoffs. In this paper, we formulate the trajectory planning as a multi-objective problem aiming to minimize both the UAV's energy consumption and the handoff rate, constrained by the UAV battery size and disconnectivity rate. Due to the problem's complexity, we propose a dynamic programming based solution. Through simulations, we demonstrate the efficiency of our approach in providing optimized UAV trajectories. Also, the impact of several parameters, such as the cargo-UAV altitude, disconnectivity rate, and type of environment, are investigated. The obtained results allow to draw recommendations and guidelines for cargo-UAV operations. Comment: This paper was presented in IEEE ICC 2021. It was awarded the "Best Paper Award"