jmc

The first few prime numbers are: $2,3,5,7,11,13,17,\dots$. Since the triangle is scalene, all the sides are different primes.

If one side is 2, then the other two sides must be odd. Then the perimeter of the triangle would be even. But the perimeter must also be greater than 2, so it cannot be prime. This means that none of the sides can be 2.

Now, suppose one side is 3. Let the other two sides be $p$ and $q,$ where $p<q.$ Since all the sides are different, $$3<p<q.$$Also, by the Triangle Inequality, $p+3>q,$ so $$p>q-3.$$Since $p<q,$ the only possible values of $p$ are $q-2$ and $q-1.$

Since $p$ is a prime greater than 3, $p$ is odd. If $p=q-1,$ then $q=p+1$ is even, which means $q$ is not prime. Therefore, $p=q-2,$ or $$q=p+2.$$As a number, $p$ must be of the form $3k,$ $3k+1,$ or $3k+2.$ Since $p$ is prime, $p$ cannot be of the form $3k.$ If $p=3k+1,$ then $q=p+2=3k+3=3(k+1),$ which is not prime. Therefore, $p=3k+2.$ Then $q=p+2=3k+4,$ and the perimeter of the triangle is $$p+q+3=(3k+2)+(3k+4)+3=6k+9=3(2k+3).$$Since this is divisible by 3, the perimeter cannot be prime. This tells us that none of the sides can be equal to 3 either.

Note that $5+7+11=23$ is prime, so the smallest possible perimeter is $\boxed{23}.$