TSTST 2013 Problem 5

Let $p$ be a prime. Prove that in a complete graph with $1000 p$ vertices whose edges are labelled with integers, one can find a cycle whose sum of labels is divisible by $p$.