Since
$$\frac{3^l}{10^4} - \left\lfloor \frac{3^l}{10^4} \right\rfloor = \frac{3^m}{10^4} - \left\lfloor \frac{3^m}{10^4} \right\rfloor = \frac{3^n}{10^4} - \left\lfloor \frac{3^n}{10^4} \right\rfloor,$$
we have
$$\begin{align} 3^l &\equiv 3^m \equiv 3^n \pmod{10^4} \\ &\iff \begin{cases} 3^l \equiv 3^m \equiv 3^n \pmod{2^4}, \\ 3^l \equiv 3^m \equiv 3^n \pmod{5^4}. \end{cases} \tag{1} \end{align}$$
As $(3, 2) = 1$, we then have from $(1)$ $3^{l-n} \equiv 3^{m-n} \equiv 1 \pmod{2^4}$.
Let $u$ be the minimum positive integer satisfying $3^u \equiv 1 \pmod{2^4}$.
Then for every positive integer $v$ satisfying $3^v \equiv 1 \pmod{2^4}$, we must have $u \mid v$. Otherwise, if $u \nmid v$, then using division with a remainder we could get two non-negative integers $a$ and $b$ satisfying $v = au + b$ with $0 < b < u$. Then $3^b \equiv 3^{au+b} \equiv 3^v \equiv 1 \pmod{2^4}$, contradicting the definition of $u$. Therefore $u \mid v$.
Notice that
$$3 \equiv 3 \pmod{2^4},\ 3^2 \equiv 9 \pmod{2^4},$$
$$3^3 \equiv 27 \equiv 11 \pmod{2^4},\ 3^4 \equiv 1 \pmod{2^4},$$
then $u = 4$. We may assume that $m-n = 4k$, where $k$ is a positive integer.
In the same way, we get from $(2)$ $3^{m-n} \equiv 1 \pmod{5^4}$, that is,
$3^{4k} \equiv 1 \pmod{5^4}$.
Now, we are going to find number $k$. As $3^{4k}-1 = (1+5 \times 2^4)^k - 1 = 0 \pmod{5^4}$, i.e.
$$\begin{aligned} & 5k \times 2^4 + \frac{k(k-1)}{2} \times 5^2 \times 2^8 + \frac{k(k-1)(k-2)}{6} \times 5^3 \times 2^{12} \\ &= 5k + 5^2 k [3 + (k-1) \times 2^7] + \frac{k(k-1)(k-2)}{3} \times 5^3 \times 2^{11} \\ &= 0 \pmod{5^4}, \end{aligned}$$
so $k = 5t$. Substituting in the above expression, we get
$$t + 5t[3 + (5t - 1) \times 2^7] \equiv 0 \pmod{5^2}.$$
Then $k = 5t = 5^3 s$, and $m-n = 500s$, where $s$ is a positive integer.
In the same way, we get $l-n = 500r$, where $r$ is a positive integer and $r > s$ since $l > m > n$.
So the three sides of the required triangle are $l = 500r + n$, $m = 500s + n$ and $n$, respectively, satisfying $n > l-n = 500(r-s)$. When $s=1$, $r=2$ the perimeter reaches the minimum which equals $(1000+501)+(500+501)+501 = 3003$.