Example 1 Let $m, n$ be positive integers, and $p$ be a prime. Find all triples $(m, n, p)$ that satisfy $\mathrm{C}_{m}^{3}-4=p^{n}$.
Notice that,
$$
\begin{array}{l}
\mathrm{C}_{m}^{3}-4=\frac{m(m-1)(m-2)-24}{6} \\
=\frac{(m-4)\left(m^{2}+m+6\right)}{6} .
\end{array}
$$

Thus, $m>4$.
$$
\begin{array}{l}
\text { Also, }\left(m-4, m^{2}+m+6\right)=\left(m-4,4^{2}+4+6\right) \\
=(m-4,26),
\end{array}
$$

Therefore, we discuss three cases.
(1) $p \neq 2,13$.
In this case, $\left(m-4, m^{2}+m+6\right)=1$, so one of $m-4$ or $m^{2}+m+6$ must be a divisor of 6.
Since $m^{2}+m+6>6$, we have $(m-4) \mid 6$.
Thus, $m-4=1,2,3,6$.
When $m-4=1$, i.e., $m=5$,
$$
\mathrm{C}_{m}^{3}-4=\frac{(5-4)\left(5^{2}+5+6\right)}{6}=6 \neq p^{n} \text {, }
$$

which does not satisfy the condition.
When $m-4=2$, i.e., $m=6$,
$$
\mathrm{C}_{m}^{3}-4=\frac{(6-4)\left(6^{2}+6+6\right)}{6}=16=2^{4} \text {, }
$$

we obtain a solution $(m, n, p)=(6,4,2)$.
When $m-4=3$, i.e., $m=7$,
$$
C_{m}^{3}-4=\frac{(7-4)\left(7^{2}+7+6\right)}{6}=31 \text {, }
$$

we obtain a solution $(m, n, p)=(7,1,31)$.
When $m-4=6$, i.e., $m=10$,
$$
\begin{array}{l}
\mathrm{C}_{m}^{3}-4=\frac{(10-4)\left(10^{2}+10+6\right)}{6} \\
=116 \neq p^{n},
\end{array}
$$

which does not satisfy the condition.
(2) $p=2$.
In this case, $(m-4)\left(m^{2}+m+6\right)=3 \times 2^{n+1}$.
(i) If $m-4=3 \times 2^{s}>4$,
$m^{2}+m+6=2^{t} \geqslant 8$,
$s+t=n+1$

Since $\left(m-4, m^{2}+m+6\right) \mid 26$, we have
$\left(m-4, m^{2}+m+6\right)=2$
$\Rightarrow s, t$ with the smaller one being 1
$\Rightarrow s=1, m=10$.
From (1), we know this is not valid.
(ii) If $m^{2}+m+6=3 \times 2^{t}>6$,
$m-4=2^{s} \geqslant 2$,
$s+t=n+1$,

Since $\left(m-4, m^{2}+m+6\right) \mid 26$, we have
$\left(m-4, m^{2}+m+6\right)=2$
$\Rightarrow s, t$ with the smaller one being 1
$\Rightarrow s=1, m=6$.
Then $\mathrm{C}_{m}^{3}-4=\frac{(6-4)\left(6^{2}+6+6\right)}{6}=2^{4}$.
Thus, $(m, n, p)=(6,4,2)$, which satisfies the condition.
(3) $p=13$.
(i) If $\left(m-4, m^{2}+m+6\right)=1$ or 2, then one of $m-4$ or $m^{2}+m+6$ must be $13^{n}$.
If $m-4=13^{n}$, then $\left(m^{2}+m+6\right) \mid 6$, which is a contradiction;
If $m^{2}+m+6=13^{n}$, then $(m-4) \mid 6$, similar to (1), there are no new solutions that satisfy the condition.
(ii) If $\left(m-4, m^{2}+m+6\right)=13$ or 26, then let $m-4=13^{s} k$, i.e., $m=13^{s}+4$.
Thus, $m^{2}+m+6$
$$
\begin{array}{l}
=\left(13^{s} k+4\right)^{2}+13^{s} k+4+6 \\
=13^{s s} k^{2}+8 \times 13^{s} k+16+13^{s} k+4+6 \\
=13^{2 s} k^{2}+9 \times 13^{\prime} k+26,
\end{array}
$$
$\operatorname{ord}_{13}(m-4)$ and $\operatorname{ord}_{13}\left(m^{2}+m+6\right)$ must have at least one equal to 1, where $\operatorname{ord}_{p} q$ denotes the power of the prime $p$ in the integer $q$.

If $\operatorname{ord}_{13}(m-4)=1$, then $m-4$ can only be $13, 13 \times 2, 13 \times 3, 13 \times 4$, i.e., $m=17,30,43,56$, and none of these satisfy the condition upon inspection;

If $\operatorname{ord}_{13}\left(m^{2}+m+6\right)=1$, then $m^{2}+m+6$ can only be $13, 13 \times 2, 13 \times 3, 13 \times 4$, i.e.,
$$
m=\frac{-1 \pm \sqrt{29}}{2}, 4,-5, \frac{-1 \pm \sqrt{133}}{2}, 6,-7 \text {, }
$$

and none of these satisfy the condition upon inspection.
In summary, the triples that satisfy the condition are
$(m, n, p)=(7,1,31),(6,4,2)$.