An abundance of a's

Note that

$m^5-m\equiv0\pmod{30}$ .

That follows immediately from Fermat's theorem (use it for 2,3 and 5).

Then

$a_1^5+a_2^5+...+a_n^5\equiv a_1+a_2+...+a_n\pmod{30}$ .

But the left side is simply 2004, which is congruent to 24 modulo 30.

So $a_1+a_2+...a_n=30k+24$

When k=0, we can give

$a_1=4, a_2=a_3=a_4=a_5=3$ and $a_6=a_7=...=a_{13}=1$ as an example.

So the minimum is $\boxed{24}$