Solution:
Without loss of generality let $x > y$. We must have $z^{3}$ expressible as the sum of two squares, and this first happens when $z = 5$. Then $x$ and $y$ can be $10$ and $5$ or $11$ and $2$. If $z > 5$ then $z \geq 10$ for $z^{3}$ to be a sum of two distinct squares, so $x^{2} > 500$, $x > 22$, so $x + y + z > 32$. Thus the smallest possible value of $x + y + z$ is $11 + 2 + 5 = \mathbf{18}$.

Solution:
If $z > 5$, then $z \geq 6$, so $z^{3} \geq 216$. Now $x^{2} + y^{2} \geq 216$, so $x \geq 11$ and $y \geq 1$, thus $x + y + z \geq 18$. Since $x = 11$, $y = 1$, $z = 6$ does not work, we must have $x + y + z > 18$, and the solution given is the best possible.