Faits: Faits: A. M._, né en 1966, marié et père de quatre enfants, travaillait comme chef d'équipe au service de l'entreprise X._. En raison de problèmes dorsaux et, par la suite, d'un état dépressif, il a été mis en arrêt de travail à 50 % du 2 février au 14 mai 2000, puis à 100 % dès cette date. Son contrat de travail a pris fin le 30 novembre suivant. Le 6 février 2001, M._ a présenté une demande de prestations de l'assurance-invalidité. Dans un rapport du 20 juin 2001, le docteur S._, médecin traitant, a fait état de lombosciatalgies gauches chroniques, d'une hernie discale para-médiane gauche L5-S1, d'une oesophagite de stade IV actuellement guérie, ainsi que d'une dépression; il a déclaré que son patient était inapte à poursuivre un travail de vigneron mais qu'il serait en mesure d'exercer à 50 % une activité évitant les positions statiques prolongées, les situations de stress et le port de charges supérieures à 15 kg. D'autres documents médicaux (émanant des docteurs W._ et C._) ont également été versés au dossier. Sur demande de l'Office AI du canton du Valais (ci-après: l'office AI), l'assuré a été examiné par les docteurs B._, de la Clinique Y._, P._, neurologue, et A._, psychiatre (voir leurs rapports respectifs des 21 novembre 2002, 7 février et 15 mai 2003). Au terme d'un entretien de synthèse avec ses confrères somaticiens, le docteur A._ a posé le diagnostic principal de troubles somatoformes douloureux; il n'a pas retenu d'incapacité de travail. Par décision du 20 mai 2003 l'office AI a rejeté la demande de prestations. Saisi d'une opposition, il l'a écartée dans une nouvelle décision du 25 juillet 2003. Dans un rapport du 20 juin 2001, le docteur S._, médecin traitant, a fait état de lombosciatalgies gauches chroniques, d'une hernie discale para-médiane gauche L5-S1, d'une oesophagite de stade IV actuellement guérie, ainsi que d'une dépression; il a déclaré que son patient était inapte à poursuivre un travail de vigneron mais qu'il serait en mesure d'exercer à 50 % une activité évitant les positions statiques prolongées, les situations de stress et le port de charges supérieures à 15 kg. D'autres documents médicaux (émanant des docteurs W._ et C._) ont également été versés au dossier. Sur demande de l'Office AI du canton du Valais (ci-après: l'office AI), l'assuré a été examiné par les docteurs B._, de la Clinique Y._, P._, neurologue, et A._, psychiatre (voir leurs rapports respectifs des 21 novembre 2002, 7 février et 15 mai 2003). Au terme d'un entretien de synthèse avec ses confrères somaticiens, le docteur A._ a posé le diagnostic principal de troubles somatoformes douloureux; il n'a pas retenu d'incapacité de travail. Par décision du 20 mai 2003 l'office AI a rejeté la demande de prestations. Saisi d'une opposition, il l'a écartée dans une nouvelle décision du 25 juillet 2003. B. M._ a déféré cette décision au Tribunal cantonal valaisan des assurances, qui l'a débouté par jugement du 3 novembre 2003. En substance, le tribunal a fait siennes les conclusions des experts mandatés par l'office AI et retenu que l'assuré ne subissait aucune incapacité de travail significative en raison d'une atteinte psychique ou physique ouvrant le droit à des prestations de l'assurance-invalidité. B. M._ a déféré cette décision au Tribunal cantonal valaisan des assurances, qui l'a débouté par jugement du 3 novembre 2003. En substance, le tribunal a fait siennes les conclusions des experts mandatés par l'office AI et retenu que l'assuré ne subissait aucune incapacité de travail significative en raison d'une atteinte psychique ou physique ouvrant le droit à des prestations de l'assurance-invalidité. C. M._ interjette recours de droit administratif contre ce jugement, dont il requiert l'annulation. Sous suite de frais et dépens, il conclut au renvoi du dossier pour instruction complémentaire. L'office AI conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer. L'office AI conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer. D. Après la clôture de l'échange d'écritures, M._ a produit un nouveau rapport médical (du 17 juin 2004) émanant du service de rhumatologie de la Clinique Z._. 