Faits: Faits: A. A._, née en 1986, est affiliée à la Mutuelle Valaisanne (ci-après : la Mutuelle) notamment pour l'assurance obligatoire des soins. Par lettre du 7 décembre 2001, la doctoresse F._, gynécologue, a informé la Mutuelle que l'assurée présentait une importante malformation mammaire (hypoplasie bilatérale très marquée avec forme tubulaire et hypertrophie aréolaire relative) qui la perturbait fortement sur le plan psychique. La prescription de la pilule pour augmenter le volume de la glande mammaire n'avait donné aucun résultat, si bien qu'il y avait, d'après ce médecin, une indication médicale à une correction mammaire. A cette lettre était joint l'avis du docteur M._, spécialiste en chirurgie plastique et reconstructive, selon lequel l'état de A._ «n'était pas acceptable pour une jeune fille» et justifiait une opération immédiate, même si on ne pouvait exclure ultérieurement la nécessité de retouches. Ayant examiné l'assurée, le docteur O._, médecin-conseil de la Mutuelle, a conclu qu'elle présentait des «troubles psychologiques de circonstance» liés à sa malformation mammaire «sans aucun doute inesthétique», mais aucun symptôme à caractère de maladie nécessitant un traitement (rapport du 19 février 2002). Sur cette base, la Mutuelle a fait part de son refus de prendre en charge l'intervention envisagée, au motif que celle-ci relevait de la chirurgie esthétique et ne constituait donc pas une prestation obligatoirement à charge des caisses-maladie (lettre du 28 février 2002). A._ a manifesté son désaccord avec la position de son assureur-maladie et produit d'autres documents médicaux (des docteurs C._, pédopsychiatre, Z._, gynécologue, et I._, spécialiste en chirurgie plastique et reconstructive). Le 24 février 2003, la Mutuelle a rendu une décision dans le sens de ses précédentes déclarations. Saisie d'une opposition, elle l'a écartée dans une nouvelle décision du 8 mai 2003. Entre-temps, l'opération a été pratiquée le 18 mars 2003 au Centre de chirurgie esthétique et réparatrice de l'Hôpital X._ par le docteur I._. Ayant examiné l'assurée, le docteur O._, médecin-conseil de la Mutuelle, a conclu qu'elle présentait des «troubles psychologiques de circonstance» liés à sa malformation mammaire «sans aucun doute inesthétique», mais aucun symptôme à caractère de maladie nécessitant un traitement (rapport du 19 février 2002). Sur cette base, la Mutuelle a fait part de son refus de prendre en charge l'intervention envisagée, au motif que celle-ci relevait de la chirurgie esthétique et ne constituait donc pas une prestation obligatoirement à charge des caisses-maladie (lettre du 28 février 2002). A._ a manifesté son désaccord avec la position de son assureur-maladie et produit d'autres documents médicaux (des docteurs C._, pédopsychiatre, Z._, gynécologue, et I._, spécialiste en chirurgie plastique et reconstructive). Le 24 février 2003, la Mutuelle a rendu une décision dans le sens de ses précédentes déclarations. Saisie d'une opposition, elle l'a écartée dans une nouvelle décision du 8 mai 2003. Entre-temps, l'opération a été pratiquée le 18 mars 2003 au Centre de chirurgie esthétique et réparatrice de l'Hôpital X._ par le docteur I._. B. Par jugement du 2 décembre 2003, le Tribunal cantonal valaisan des assurances a admis le recours formé par A._ contre la décision sur opposition du 8 mai 2003, et condamné la Mutuelle à rembourser la totalité des frais de l'intervention, par 8'078 fr., sous déduction d'une éventuelle franchise résiduelle et de la quote-part due par l'assurée. B. Par jugement du 2 décembre 2003, le Tribunal cantonal valaisan des assurances a admis le recours formé par A._ contre la décision sur opposition du 8 mai 2003, et condamné la Mutuelle à rembourser la totalité des frais de l'intervention, par 8'078 fr., sous déduction d'une éventuelle franchise résiduelle et de la quote-part due par l'assurée. C. La Mutuelle interjette recours de droit administratif contre ce jugement, dont elle requiert l'annulation. Elle invite le Tribunal fédéral des assurances à dire qu'elle n'est pas tenue de prendre en charge les frais liés à l'opération de construction mammaire subie par A._. Celle-ci conclut au rejet du recours, tandis que l'Office fédéral de la santé publique a renoncé à se déterminer. 