(1) Find the general term formula of the sequence $\left\{a_{n}\right\}$;
(2) Let $b_{n}=a_{n}^{2}+2 a_{n}+3, n \in \mathbf{N}_{+}$, try to find
$$
M=a_{m}^{2}+b_{n}^{2}+m^{2}+n^{2}-2\left(a_{m} b_{n}+m n\right)
$$
$\left(m 、 n \in \mathbf{N}_{+}\right)$ the minimum value.
(1) It is easy to know that when $n \geqslant 2, n \in \mathbf{N}_{+}$, we have
$4\left(S_{n}-S_{n-1}\right)=\left(a_{n}+1\right)^{2}-\left(a_{n-1}+1\right)^{2}$.
Thus, $\left(a_{n}+a_{n-1}\right)\left(a_{n}-a_{n-1}-2\right)=0$.
Since $a_{n}+a_{n-1}>0$, it follows that,
$$
a_{n}-a_{n-1}=2 \text {. }
$$

It is easy to see that $a_{1}=1, a_{2}=3$, so $\left\{a_{n}\right\}$ is an arithmetic sequence with a common difference of 2. Therefore,
$$
a_{n}=1+2(n-1)=2 n-1 .
$$
(2) Since $a_{n}=2 n-1$, we have,
$$
b_{n}=(2 n-1)^{2}+2(2 n-1)+3=4 n^{2}+2 \text {. }
$$

The distance from a point $\left(x_{0}, 4 x_{0}^{2}+2\right)\left(x_{0} \geqslant 1\right)$ on the parabola $y=4 x^{2}+2$ to the line $y=2 x-1$ is
$$
\begin{array}{l}
d=\frac{\left|2 x_{0}-\left(4 x_{0}^{2}+2\right)-1\right|}{\sqrt{5}}=\frac{\left(2 x_{0}-\frac{1}{2}\right)^{2}+\frac{11}{4}}{\sqrt{5}} \\
\geqslant \frac{\left(2 \times 1-\frac{1}{2}\right)^{2}+\frac{11}{4}}{\sqrt{5}}=\sqrt{5},
\end{array}
$$

When $x_{0}=1$, $d_{\text {min }}=\sqrt{5}$.
It is easy to see that $M=\left(a_{m}-b_{n}\right)^{2}+(m-n)^{2}$ represents the square of the distance between the point $\left(n, b_{n}\right)$ on the parabola $y=4 x^{2}+2$ and the point $\left(m, a_{m}\right)$ on the line $y=2 x-1$. Clearly, $M \geqslant d_{\text {min }}^{2}=5$.

Considering that when $x_{0}=1$, $y_{0}=4 x_{0}^{2}+2=6$, the point $(1,6)$ lies on the parabola, which is also the point corresponding to the first term of the sequence $\left\{b_{n}\right\}$. Drawing a perpendicular from the point $(1,6)$ to the line $y=2 x-1$, let the foot of the perpendicular be $(x, 2 x-1)$. We have
$$
(x-1)^{2}+(2 x-1-6)^{2}=d_{\min }^{2}=5 .
$$

Solving this, we get $x=3$.
Thus, the foot of the perpendicular is $(3,5)$, which corresponds to $a_{3}=5$ in the sequence $\left\{a_{n}\right\}$.
Therefore, when $m=3, a_{m}=5, n=1, b_{n}=6$,
$$
M_{\text {min }}=d_{\text {min }}^{2}=5 \text {. }
$$