I have found a nice answer here.
The random walker can get from $x_i$ to $x_j$ either directly in one step with probability $P_{ij}$, or it first goes from $x_i$ to $x_k$ ($k\ne j)$ with probability $P_{ik}$ and the expected time to get to $x_j$ is $1+M_{kj}$. Formally:
\begin{align}
M_{ij}&=P_{ij}+\sum_{k\ne j}P_{ij}(1+M_{ij})\\
&=1+\sum_{k=1}^n P_{ij}M_{kj}-P_{ij}M_{jj}
\end{align}
One can observe that
$$M=E+P(M-M_d)\tag{1}\label{1}$$
where $E=11^\top$ and $M_d$ is the diagonal matrix with entries $M_{11},\dots,M_{nn}$.
First, we want to figure out $M_d$. To that end, let $\psi=\begin{pmatrix}d_1&\dots&d_n\end{pmatrix}^\top$, this is a left eigenvector of $P$:
$$\psi^\top P=\psi$$
We get:
\begin{align}
\psi^\top M&=\psi^\top E+\psi^\top A(M-M_d)\\
&=\psi^\top E+\psi^\top(M-M_d)
\end{align}
Thus, we have
$$\psi^\top M_d=\psi^\top E=\psi^\top 11^\top=\left(\sum_{i=1}^kd_k\right)1^\top$$
equivalently,
$$d_iM_{ii}=\sum_{k=1}^nd_k$$
Hence,
$$M_{ii}=\frac{1}{d_k}\sum_{k=1}^n d_k=\frac{vol(G)}{d_k}$$
Now, we assume $P$ is irreducible, then the solution $M$ to \eqref{1} is unique:
Assume $M'$ is another solution:
$$M'=E+P(M'-M_d)$$
then
$$M-M'=P(M-M')$$
The columns on $M-M'$ are right eigenvectors of $P$ with eigenvalue $1$. But if $P$ is irreducible, the only eigenvector with eigenvalue $1$ is the all-ones vector. Therefore,
$$M-M'=1u^\top$$
for some $u$. However, $diag(M)=diag(M')=M_d$. Therefore, $u=0$ and $M=M'$.
Now, the mean first passage time matrix can be written as
$$T=M-M_d$$
Therefore, \eqref{1} is equivalent to
$$(I-P)T=E-M_d$$
$(I-P)$ is not invertible, however, the graph Laplacian is defined as
$$L=(D-W)=D(I-P)$$
Hence,
$$LT=DE-DM_d$$
Now,
$$\Gamma L=I-\frac{1}{n}11^\top$$
So, we get
\begin{align}
(\Gamma L)T&=\Gamma DE-\Gamma DM_d\\
T&=\Gamma DE-\Gamma DM_d+1u^\top
\end{align}
for some vector $u$.
$$T_{ij}=\sum_{k=1}^n\Gamma _{ik}d_k-vol(G)\Gamma _{ij}+u_j$$
because $DM_d=vol(G)I$. Since $T_{ii}=0$, we find
$$u_i=-\sum_{k=1}^n\Gamma _{ik}d_k+vol(G)\Gamma_{ii}$$
And from the last equations:
$$d(i,j)=T_{ij}+T_{ji}=vol(G)\left(\Gamma _{ii}+\Gamma _{jj}-2\Gamma _{ij}\right)$$
