Solution:

Write $z = a + bi$ with $a^2 + b^2 = p,$ so $p = 2$ or $p \equiv 1 \pmod 4,$ and the pair $\{|a|, |b|\}$ is then unique. Replacing $z$ by $\pm z,$ $\pm\bar{z},$ $\pm iz,$ $\pm i\bar{z}$ only changes the real and imaginary parts of $z^3$ by signs and swaps, so we may take $a \gt b \gt 0,$ and the two candidate side lengths are $|\operatorname{Re} z^3|$ and $|\operatorname{Im} z^3|.$ Expanding $z^3 = (a^3 - 3ab^2) + (3a^2b - b^3)i$ and factoring, $$\operatorname{Re} z^3 + \operatorname{Im} z^3 = (a - b)(p + 4ab), \qquad \operatorname{Re} z^3 - \operatorname{Im} z^3 = (a + b)(p - 4ab).$$ The triangle exists exactly when $\bigl||\operatorname{Re}| - |\operatorname{Im}|\bigr| \lt p \lt |\operatorname{Re}| + |\operatorname{Im}|,$ and those two quantities are, in some order, the absolute values above. Since $a \gt b$ forces $(a - b)(p + 4ab) \gt p,$ the whole condition reduces to $(a + b)\,|p - 4ab| \lt p.$

Because $a + b \gt \sqrt{a^2 + b^2} = \sqrt{p},$ this requires $|p - 4ab| \lt \sqrt{p} \lt 32:$ the products $4ab$ and $a^2 + b^2$ must nearly coincide. Checking the primes $p \equiv 1 \pmod 4$ below $1000$ from the top down, each with its unique representation (for instance $997 = 31^2 + 6^2$ gives $(a+b)|p - 4ab| = 37 \cdot 253,$ far too big), the condition fails for every prime greater than $349$ and holds for $349 = 18^2 + 5^2,$ where $(a + b)\,|p - 4ab| = 23 \cdot |349 - 360| = 253 \lt 349.$

Indeed for $z = 18 + 5i$ we get $z^3 = 4482 + 4735i,$ and the lengths $349,$ $4482,$ $4735$ form a valid triangle. The answer is $349.$