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$. This was proved by Wielandt, although this proof was not published. He claimed the result in H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z., 52, 642–648 (1950). 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]: https://math.stackexchange.com/questions/450090/if-p-is-a-regular-transition-probability-matrix-then-pn2-has-no-zero-ele