ELMO 2023 Problem 1

Let $m$ be a positive integer. Find, in terms of $m$, all polynomials $P(x)$ with integer coefficients such that for every integer $n$, there exists an integer $k$ such that $P(k)=n^m$.

Proposed by Raymond Feng