Faits:
Faits:
A. A.a Par décision du 5 juillet 1996, l'Office AI du canton du Valais (ci-après : l'office AI) a rejeté la demande de prestations présentée le 29 mars 1995 par M._, né en 1957. Saisi d'un recours de l'assuré, le Tribunal cantonal valaisan des assurances a annulé cette décision et renvoyé la cause à l'administration pour un complément d'instruction médicale (jugement du 25 septembre 1997). Par arrêt du 28 juin 1998, le Tribunal fédéral des assurances a partiellement admis le recours de droit administratif interjeté par M._ et réformé le jugement entrepris au sens des considérants. L'office AI a repris l'instruction du dossier conformément aux injonctions reçues et rendu une nouvelle décision, le 14 novembre 2001, par laquelle il a derechef refusé à l'assuré le droit à des prestations. Cette décision, confirmée par jugement cantonal du 2 septembre 2002, est entrée en force.
A.b Le 14 novembre 2002, M._, a déposé une nouvelle demande de prestations, invoquant une aggravation de son état de santé et demandant une rente à partir de juillet 2001. Plusieurs rapports médicaux ont été versés au dossier (notamment des docteurs B._, A._ et F._ du Centre hospitalier X._). Appelé à donner son avis sur le cas, le docteur T._, médecin-conseil de l'office AI, a préconisé la mise en oeuvre d'une expertise médicale. Par communication du 3 novembre 2003, l'office AI a informé l'assuré de la nécessité d'organiser une expertise pluridisciplinaire et indiqué qu'il serait convoqué à cette fin par le Centre d'observation médicale de l'AI (COMAI). Par lettre du 17 novembre suivant, M._ s'est opposé au principe d'une nouvelle mesure d'instruction médicale, faisant valoir que son état de santé était suffisamment élucidé.
Par «décision incidente» du 28 novembre 2003, l'office AI a écarté les objections du prénommé et confirmé le mandat d'expertise au COMAI.
Par «décision incidente» du 28 novembre 2003, l'office AI a écarté les objections du prénommé et confirmé le mandat d'expertise au COMAI.
B. Par jugement du 24 mars 2004, le Tribunal cantonal valaisan des assurances a partiellement admis le recours formé par l'assuré contre cette dernière décision, annulé celle-ci et renvoyé la cause à l'office AI à charge pour lui d'en compléter l'instruction dans le sens des considérants.
B. Par jugement du 24 mars 2004, le Tribunal cantonal valaisan des assurances a partiellement admis le recours formé par l'assuré contre cette dernière décision, annulé celle-ci et renvoyé la cause à l'office AI à charge pour lui d'en compléter l'instruction dans le sens des considérants.
C. L'office AI interjette recours de droit administratif contre ce jugement, dont il requiert l'annulation. Il conclut à la confirmation de sa décision du 28 novembre 2003.
Sous suite de dépens, M._ conclut, principalement, à l'irrecevabilité du recours et, subsidiairement, à son rejet. L'Office fédéral des assurances sociales a renoncé à se déterminer.

Considérant en droit:
Considérant en droit:
1. Selon l'art. 128 OJ, le Tribunal fédéral des assurances connaît en dernière instance des recours de droit administratif contre des décisions au sens des art. 97, 98 let. b à h et 98a OJ, en matière d'assurances sociales. Quant à la notion de décision pouvant faire l'objet d'un recours de droit administratif, l'art. 97 OJ renvoie à l'art. 5 PA (cf. aussi l'art. 49 al. 1 LPGA; <ref-ruling> consid. 2.3). Selon le premier alinéa de cette disposition, sont considérées comme décisions les mesures prises par les autorités dans des cas d'espèce, fondées sur le droit public fédéral et ayant pour objet de créer, de modifier ou d'annuler des droits ou des obligations, de constater l'existence, l'inexistence ou l'étendue de droits ou d'obligations, de rejeter ou de déclarer irrecevables des demandes tendant à créer, modifier, annuler ou constater des droits ou obligations.
1. Selon l'art. 128 OJ, le Tribunal fédéral des assurances connaît en dernière instance des recours de droit administratif contre des décisions au sens des art. 97, 98 let. b à h et 98a OJ, en matière d'assurances sociales. Quant à la notion de décision pouvant faire l'objet d'un recours de droit administratif, l'art. 97 OJ renvoie à l'art. 5 PA (cf. aussi l'art. 49 al. 1 LPGA; <ref-ruling> consid. 2.3). Selon le premier alinéa de cette disposition, sont considérées comme décisions les mesures prises par les autorités dans des cas d'espèce, fondées sur le droit public fédéral et ayant pour objet de créer, de modifier ou d'annuler des droits ou des obligations, de constater l'existence, l'inexistence ou l'étendue de droits ou d'obligations, de rejeter ou de déclarer irrecevables des demandes tendant à créer, modifier, annuler ou constater des droits ou obligations.
2. 2.1 La juridiction cantonale a implicitement considéré que la «décision incidente» prise par l'office AI le 28 novembre 2003 était une décision attaquable au sens de l'art. 5 PA et qu'elle pouvait faire l'objet d'un recours direct devant le tribunal cantonal des assurances en vertu de l'art. 52 al. 1 LPGA a contrario. Sur le fond, elle a jugé qu'au plan neurologique, la situation médicale de l'assuré était claire et qu'elle ne nécessitait donc pas des investigations supplémentaires. Elle a en revanche admis qu'il fallait requérir des éclaircissements sur trois au-tres points : l'éventualité d'une atteinte à la santé psychique, les effets de l'herpès récidivant dont l'assuré était atteint au visage, et enfin l'opportunité d'une intervention chirurgicale pour traiter les troubles radiculaires. Pour répondre à ces questions, l'office AI était invité à mandater deux experts pratiquant dans la région où habitait l'assuré, de même qu'à recueillir des renseignements complémentaires auprès du docteur D._, médecin traitant, pour l'atteinte dermatologique.
2.2 En substance, l'office AI fait valoir qu'une expertise pluridisciplinaire par le COMAI constitue au contraire la mesure d'instruction la plus appropriée pour statuer sur les droits de M._. Lorsqu'un assuré souffrait de plusieurs atteintes à la santé différentes comme en l'espèce, il était plus judicieux d'examiner la situation selon une approche pluridisciplinaire, plutôt que de faire appel à divers experts indépendants.
2.3 L'intimé, pour sa part, soutient que le jugement cantonal n'est pas susceptible de faire l'objet d'un recours séparé de la part de l'administration, faute de remplir les conditions posées par l'art. 45 al. 2 let. f PA. Au surplus, il estime que les modalités des mesures d'instruction complémentaire prescrites par les premiers juges ne prêtent pas flanc à la critique.
2.3 L'intimé, pour sa part, soutient que le jugement cantonal n'est pas susceptible de faire l'objet d'un recours séparé de la part de l'administration, faute de remplir les conditions posées par l'art. 45 al. 2 let. f PA. Au surplus, il estime que les modalités des mesures d'instruction complémentaire prescrites par les premiers juges ne prêtent pas flanc à la critique.
3. Le Tribunal fédéral des assurances examine d'office les conditions dont dépend la qualité pour recourir et les conditions formelles de validité et de régularité de la procédure administrative, soit en particulier le point de savoir si c'est à juste titre que la juridiction cantonale est entrée en matière sur le recours ou l'action. Cela vaut également pour l'examen de la compétence quant au fond de l'autorité qui a statué. Aussi, lorsque l'autorité de première instance a ignoré qu'une condition de l'examen du litige par le juge faisait défaut et a statué sur le fond, cela doit conduire le tribunal saisi d'un recours à annuler d'office le jugement entrepris en constatant qu'on ne peut entrer en matière sur le moyen de droit, dès lors que les conditions de l'examen du litige par le juge ne sont pas réalisées (<ref-ruling> consid. 4a; voir aussi <ref-ruling> consid. 2a et les références).
3. Le Tribunal fédéral des assurances examine d'office les conditions dont dépend la qualité pour recourir et les conditions formelles de validité et de régularité de la procédure administrative, soit en particulier le point de savoir si c'est à juste titre que la juridiction cantonale est entrée en matière sur le recours ou l'action. Cela vaut également pour l'examen de la compétence quant au fond de l'autorité qui a statué. Aussi, lorsque l'autorité de première instance a ignoré qu'une condition de l'examen du litige par le juge faisait défaut et a statué sur le fond, cela doit conduire le tribunal saisi d'un recours à annuler d'office le jugement entrepris en constatant qu'on ne peut entrer en matière sur le moyen de droit, dès lors que les conditions de l'examen du litige par le juge ne sont pas réalisées (<ref-ruling> consid. 4a; voir aussi <ref-ruling> consid. 2a et les références).
4. 4.1 En ce qui concerne la procédure administrative suivie par les offi-ces AI pour l'instruction de la demande sous l'empire des dispositions applicables avant l'entrée en vigueur, le 1er janvier 2003, de la loi fédérale sur la partie générale des assurances sociales du 6 octobre 2000 [LPGA] - en particulier les art. 58 et 86 al. 2 aLAI ainsi que les art. 69 à 77 RAI -, le Tribunal fédéral des assurances a jugé que la mise en oeuvre d'une expertise médicale n'avait pas le caractère d'une décision (<ref-ruling> consid. c; voir également l'arrêt F. du 9 février 2004, I 364/03, s'agissant de la participation de l'assuré à des mesures de réinsertion professionnelle). En effet, dès lors qu'il n'était pas possible d'obliger un assuré de se soumettre à une expertise médicale, l'acte par lequel un office AI ordonnait une telle mesure d'instruction ne portait pas sur des droits ou sur des obligations (cf. art. 75 RAI). Il s'agissait là d'une simple incombance et non pas d'une obligation juridique. En cas de refus de coopérer, l'office AI était autorisé à se prononcer en l'état du dossier, après avoir imparti à l'assuré un délai raisonnable avec indication des conséquences du défaut de collaboration (art. 73 RAI).
4.2 Selon l'art. 82 al. 1 première phrase LPGA, les dispositions maté-rielles de la loi ne sont pas applicables aux prestations en cours et aux créances fixées avant son entrée en vigueur. En revanche, les nou-velles prescriptions de procédure - à l'exception du droit procédural cantonal - s'appliquent immédiatement, dès le jour de l'entrée en vigueur de la LPGA, faute de dispositions transitoires contraires (<ref-ruling> consid. 2.2 et les arrêts cités). En l'occurrence, c'est au cours du mois de novembre 2003 que l'office AI a informé M._ de son intention de confier une expertise médicale au COMAI et qu'il a rendu, à la suite du refus du prénommé de s'y soumettre, la «décision incidente» confirmant le mandat d'expertise. Il convient par conséquent de juger le litige à l'aune de la LPGA (voir aussi arrêt R. du 25 août 2004, I 570/03, résumé dans RJB 2004, p. 749).
4.3 L'entrée en vigueur de la LPGA n'a rien changé à la notion de la décision attaquable comme objet de la contestation. Elle correspond à celle de l'art. 5 PA (<ref-ruling>). Le prononcé d'une décision reste une condition indispensable pour qu'il y ait un jugement au fond dans la procédure administrative subséquente ou dans la procédure de recours de droit administratif. Par ailleurs, sous réserve de quelques dispositions particulières qui ne jouent pas de rôle dans le présent cas - par exemple l'art. 44 LPGA, selon lequel si l'assureur doit recourir aux services d'un expert indépendant pour élucider les faits, il donne connaissance du nom de celui-ci aux parties qui peuvent récuser l'expert pour des raisons pertinentes et présenter des contre-proposi-tions -, la LPGA n'a pas apporté de changements fondamentaux dans la procédure d'instruction d'une demande de prestations AI. Elle prévoit notamment pour l'office AI le même procédé que sous l'ancien droit en cas de refus d'un assuré de se soumettre à une expertise médicale (voir art. 43 al. 3 LPGA). Ainsi, sous l'empire de la LPGA comme sous l'ancien droit, la mise en oeuvre d'une expertise médicale par un office AI ne revêt pas le caractère d'une décision administrative (sur l'ensemble de la question, voir le consid. 5 de l'arrêt B. du 8 février 2006, I 745/03, destiné à la publication dans le Recueil officiel).
Quand bien même l'intimé a intitulé sa prise de position du 28 novembre 2003 «décision incidente», c'est à tort que les premiers juges sont entrés en matière sur l'écriture de l'assuré du 11 décembre 2003, faute de décision susceptible de recours. En application de l'art. 43 LPGA (voir aussi l'art. 73 RAI à nouveau en vigueur depuis le 1er janvier 2004), l'office AI impartira un délai approprié à l'intimé pour se soumettre à l'expertise médicale ordonnée. Si celui-ci est désormais d'accord de donner suite à la convocation pour l'expertise, l'office AI se prononcera en temps voulu sur les objections de l'assuré, à savoir dans le cadre de la décision et de la décision sur opposition (cf. art. 49 al. 1 et 52 al. 1 LPGA). Dans le cas contraire, il se prononcera en l'état du dossier ou suspendra les éclaircissements et renoncera à entrer en matière.
Quand bien même l'intimé a intitulé sa prise de position du 28 novembre 2003 «décision incidente», c'est à tort que les premiers juges sont entrés en matière sur l'écriture de l'assuré du 11 décembre 2003, faute de décision susceptible de recours. En application de l'art. 43 LPGA (voir aussi l'art. 73 RAI à nouveau en vigueur depuis le 1er janvier 2004), l'office AI impartira un délai approprié à l'intimé pour se soumettre à l'expertise médicale ordonnée. Si celui-ci est désormais d'accord de donner suite à la convocation pour l'expertise, l'office AI se prononcera en temps voulu sur les objections de l'assuré, à savoir dans le cadre de la décision et de la décision sur opposition (cf. art. 49 al. 1 et 52 al. 1 LPGA). Dans le cas contraire, il se prononcera en l'état du dossier ou suspendra les éclaircissements et renoncera à entrer en matière.
5. L'intimé, qui succombe, ne saurait prétendre une indemnité de dépens pour l'instance fédérale (art. 159 al. 1 OJ en relation avec l'art. 135 OJ).

Par ces motifs, le Tribunal fédéral des assurances prononce:
Par ces motifs, le Tribunal fédéral des assurances prononce:
1. Le recours est admis en ce sens que le jugement du Tribunal cantonal valaisan des assurances du 24 mars 2004 ainsi que la décision incidente de l'Office AI du canton du Valais du 28 novembre 2003 sont annulés, la cause étant renvoyé audit office pour qu'il procède conformément aux considérants.
1. Le recours est admis en ce sens que le jugement du Tribunal cantonal valaisan des assurances du 24 mars 2004 ainsi que la décision incidente de l'Office AI du canton du Valais du 28 novembre 2003 sont annulés, la cause étant renvoyé audit office pour qu'il procède conformément aux considérants.
2. Il n'est pas perçu de frais de justice, ni alloué de dépens.
2. Il n'est pas perçu de frais de justice, ni alloué de dépens.
3. Le présent arrêt sera communiqué aux parties, au Tribunal cantonal des assurances du canton du Valais et à l'Office fédéral des assurances sociales.
Lucerne, le 10 février 2006
Au nom du Tribunal fédéral des assurances
La Présidente de la IIe Chambre: La Greffière: