Let $S_{k}=\sum_{j=1}^{n} x_{j}^{k}$, so $S_{1}=S_{2}=\cdots=S_{n-1}=1, S_{n}=2$, and $S_{m}=4$. The first of these conditions gives that $x_{1}, \ldots, x_{n}$ are the roots of $P(x)=x^{n}-x^{n-1}-c$ for some constant $c$. Then $x_{i}^{n}=x_{i}^{n-1}+c$, and thus $$2=S_{n}=S_{n-1}+c n=1+c n$$ so $c=\frac{1}{n}$. Thus, we have the recurrence $S_{k}=S_{k-1}+\frac{S_{k-n}}{n}$. This gives $S_{n+j}=2+\frac{j}{n}$ for $0 \leq j \leq n-1$, and then $S_{2 n}=3+\frac{1}{n}$. Then $S_{2 n+j}=3+\frac{2 j+1}{n}+\frac{j^{2}+j}{2 n^{2}}$ for $0 \leq j \leq n-1$. In particular, $S_{3 n-1}>4$, so we have $m \in[2 n, 3 n-1]$. Let $m=2 n+j$. Then $$3+\frac{2 j+1}{n}+\frac{j^{2}+j}{2 n^{2}}=4 \Longrightarrow 2 n^{2}-2 n(2 j+1)-\left(j^{2}+j\right)=0$$ Viewing this as a quadratic in $n$, the discriminant $4(2 j+1)^{2}+8\left(j^{2}+j\right)=24 j^{2}+24 j+4=4\left(6 j^{2}+6 j+1\right)$ must be a perfect square, so $6 j^{2}+6 j+1$ is a square. Then $$6 j^{2}+6 j+1=y^{2} \Longrightarrow 12 j^{2}+12 j+2=2 y^{2} \Longrightarrow 3(2 j+1)^{2}-2 y^{2}=1$$ The case $j=0$ gives $n=1$, a contradiction. After this, the smallest $j$ that works is $j=4$ (and $y=11$ ). Plugging this back into our quadratic, $$2 n^{2}-18 n-20=0 \Longrightarrow n^{2}-9 n-10=0$$ so $n=10$. Then $m=2 n+j=24$, so $m+n=34$.