Generalized Baxters relations on the transfer-matrices (also known as Baxters TQ relations) are constructed and proved for an arbitrary untwisted quantum affine algebra. Moreover, we interpret them as relations in the Grothendieck ring of the category O introduced by Jimbo and the second author in arXiv:1104.1891 involving infinite-dimensional representations constructed in arXiv:1104.1891, which we call here prefundamental. We define the transfer-matrices associated to the prefundamental representations and prove that their eigenvalues on any finite-dimensional representation are polynomials up to a universal factor. These polynomials are the analogues of the celebrated Baxter polynomials. Combining these two results, we express the spectra of the transfer-matrices in the general quantum integrable systems associated to an arbitrary untwisted quantum affine algebra in terms of our generalized Baxter polynomials. This proves a conjecture of Reshetikhin and the first author formulated in 1998 (arXiv:math/9810055). We also obtain generalized Bethe Ansatz equations for all untwisted quantum affine algebras.