Try to find all triples of non-negative integers $(x, y, z)$, satisfying $x \leqslant y$, and
$$
x^{2}+y^{2}=3 \cdot 2016^{z}+77 \text {. }
$$
If $z=0$, then $x^{2}+y^{2}=80$. Thus $2 x^{2} \leqslant 40 \Rightarrow x \leqslant 6$. Checking each one, we find that $(x, y, z)=(4,8,0)$ is a solution to the original equation.

Notice that $7|2016,7| 77$, taking the original equation modulo 7, we know $7 \mid x^{2}+y^{2}$. For any positive integer $a$, it is easy to see that $a^{2}$ modulo 7 has a remainder in $\{0,1,2,4\}$, and $7 \mid a^{2}$ if and only if $7 \mid a$, hence $7|x, 7| y$. Let $x=7 x_{1}, y=7 y_{1}$, substituting into the original equation, we get
$$
49\left(x_{1}^{2}+y_{1}^{2}\right)=3 \cdot 2016^{z}+77 .
$$

If $z \geqslant 2$, then $49 \mid 2016^{z}$, but $49 \nmid 77$, so $49 \nmid 3 \cdot 2016^{z}+77$, a contradiction.
If $z=1$, then equation (1) becomes $x_{1}^{2}+y_{1}^{2}=125$, thus $2 x_{1}^{2} \leqslant 125 \Rightarrow x_{1} \leqslant 7$. Checking each one, we find $\left(x_{1}, y_{1}\right)=$ $(2,11),(5,10)$, at this time $(x, y)$ are $(14,77),(35,70)$ respectively.
In summary, all the required non-negative integer triples are $(4,8,0),(14,77,1),(35,70,1)$.