Answer: 14 Consider modulo 5, we get $k\equiv\pm1\pmod5$. Clearly $k$ is even, so the first few values for $k$ are $4,6,14,16$. Note that $19^1-5^1=14$. We will prove that $19^n-5^m=4$ and $19^n-5^m=6$ do not have solutions. Suppose $19^n-5^m=4$. Consider modulo 4, we get $(-1)^n-1\equiv0\pmod4$, so $n$ is even. We get $(19^{n/2}+2)(19^{n/2}-2)=5^m$. So $19^{n/2}+2$ and $19^{n/2}-2$ are powers of 2 which differs by 4, they must be 5 and 1. So $19^{n/2}+2=5$, which is impossible. Suppose $19^n-5^m=6$. Consider modulo 5, we get $(-1)^n\equiv1\pmod5$, so $n$ is even. Consider modulo 6, we get $1-(-1)^m\equiv0\pmod6$, so $m$ is even. We get $(19^{n/2}+5^{m/2})(19^{n/2}-5^{m/2})=6$, which is impossible since $19^{n/2}+5^{m/2}\ge24>6$.