This is a combination of the [answer Gerry Myerson gave on MSE][1], the paper linked there, and the comments here.

The largest possible minimum $m$ is $(n-1)^2+1 = n^2-2n+2$. There is an essentially unique matrix showing that this is sharp, although there are many examples built from similar ideas showing that the minimum $m$ is $\Omega(n^2)$. 

$$\begin{pmatrix}0 & 0  & \cdots & 0 & 1 \newline 1 & 0 & \cdots & 0 & 0 \newline \epsilon & 1 & \cdots & 0  & 0 \newline  \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & 1 & 0 \end{pmatrix}$$

Except for the $\epsilon$, this is a circulant matrix. 

For example, let $n=8$, and set $\epsilon=1$. Here is the $40$th power:

$$\begin{pmatrix}1 & 0 & 0 & 1 & 5 & 10 & 10 & 5 \newline 5 & 1 & 0 & 0 & 1 & 5 & 10& 10 \newline 15 & 5 & 1 & 0 & 1 & 6 & 15 & 20 \newline 20 & 10 & 5 & 1 & 0 & 1 & 6 & 15 \newline 15 & 10 & 10 & 5 & 1 & 0 & 1 & 6\newline 6& 5& 10 & 10 & 5 & 1 & 0 & 1 \newline 1 & 1 & 5 & 10 & 10 & 5 & 1 & 0 \newline 0 & 0 & 1 & 5 & 10 & 10 & 5 & 1  \end{pmatrix}$$

Here is some Mathematica code you can use to animate the powers of the matrix.

    wmat[n_] := Table[If[Mod[i - j, n] == 1 || (i == 2 && j == 0), 1, 0], {i, 0, n - 1}, {j, 0, n - 1}]
    ListAnimate[Table[TableForm[MatrixPower[wmat[8], i]], {i, 1, 50}]]


  [1]: http://math.stackexchange.com/questions/450090/if-p-is-a-regular-transition-probability-matrix-then-pn2-has-no-zero-ele