Faits: Faits: A. S._ est atteint de troubles psychiques et a présenté de nombreux épisodes de polytoxicomanie. Le 15 juin 2000, il s'est annoncé à l'Office cantonal AI valaisan (OCAI), lequel lui a accordé des mesures d'ordre professionnel, sous forme d'un stage du 18 mars au 31 juillet 2000 et d'un apprentissage du 1er août 2002 au 31 juillet 2005. Par décisions des 2 mai et 27 septembre 2002, l'OCAI a fixé le montant de l'indemnité journalière allouée avec ces mesures. Par décision du 8 août 2002, il a mis l'assuré au bénéfice d'une rente d'invalidité pour la période du 1er janvier 2000 au 31 mars 2002; une part de l'arriéré de la prestation était compensée avec des prétentions du service social X._. L'assuré a recouru contre ces décisions devant le Tribunal des assurances du canton du Valais. Par jugement du 25 avril 2003, la juridiction cantonale a rejeté les recours formés contre les décisions en matière d'indemnités journalières, annulé celle portant sur la rente d'invalidité et renvoyé la cause à l'administration pour nouvelle décision; elle a considéré que le droit à la rente prenait effet au 1er décembre 1999 et que certaines compensations n'étaient pas conformes à la loi ou nécessitaient une instruction complémentaire. S._ a interjeté recours de droit administratif contre ce jugement sur la question des indemnités journalières (TFA; cause I 396/03). S._ a interjeté recours de droit administratif contre ce jugement sur la question des indemnités journalières (TFA; cause I 396/03). B. Le 26 juin 2003, S._ a demandé à l'OCAI de statuer sans attendre sur l'arriéré de rentes et la compensation. Le 4 juillet 2003, la Caisse de compensation du canton du Valais (CCC), à qui la demande avait été soumise, a informé le requérant qu'elle n'était pas à même d'établir un nouveau décompte avec précision dans l'immédiat : les pièces de son dossier avaient été transmises à Lucerne et le montant de la rente devait être diminué, vu la survenance de l'invalidité à une date antérieure. Le 8 juillet 2003, S._ a réitéré sa requête. Le 19 décembre 2003, l'assuré a déposé plainte pour déni de justice et retard injustifié contre l'OCAI et la CCC auprès de l'Office fédéral des assurances sociales. Celui-ci l'a transmise au Tribunal cantonal des assurances comme objet de sa compétence. La juridiction a interpellé l'OCAI et lui a fixé un délai pour se déterminer. Le 28 janvier 2004, la CCC a avisé le recourant qu'elle lui versait le jour même un montant provisoire de 7'000 fr. et qu'elle allait procéder aux mesures d'instructions requises à réception de son dossier. Par décision du 17 mars 2004, l'OAI a fixé le montant de la rente d'invalidité due à partir du 1er décembre 1999 et fixé - après compensations - à 2'850 fr. la quotité du solde de la prestation au 31 mars 2002. Le 23 mars 2004, la juridiction cantonale a rayé la cause du rôle le 23 mars 2004, sans allouer de dépens au recourant. La juridiction a interpellé l'OCAI et lui a fixé un délai pour se déterminer. Le 28 janvier 2004, la CCC a avisé le recourant qu'elle lui versait le jour même un montant provisoire de 7'000 fr. et qu'elle allait procéder aux mesures d'instructions requises à réception de son dossier. Par décision du 17 mars 2004, l'OAI a fixé le montant de la rente d'invalidité due à partir du 1er décembre 1999 et fixé - après compensations - à 2'850 fr. la quotité du solde de la prestation au 31 mars 2002. Le 23 mars 2004, la juridiction cantonale a rayé la cause du rôle le 23 mars 2004, sans allouer de dépens au recourant. C. S._ interjette recours de droit administratif contre ce jugement. Sous suite de dépens, il en demande l'annulation et conclut à ce qu'il soit constaté que «le retard mis par l'OCAI respectivement la CCC à se plier aux points non contestés du jugement du TCA du 25 avril 2003 et à rendre, respectivement notifier leurs nouvelles décisions a été, jusqu'à la reprise de l'instruction après le dépôt de la plainte pour déni de justice et retard injustifié de M. S._ du 19 décembre 2003, injustifié et contraire aux garanties données par la Convention européenne des droits de l'homme et la Constitution fédérale». Le recourant demande en outre que le dossier soit renvoyé au Tribunal cantonal des assurances pour qu'il statue sur les dépens de la procédure cantonale. L'OCAI et la CCC concluent au rejet du recours. Selon la CCC, un nouveau calcul du montant de la rente devait être effectué en fonction d'un nouveau prononcé de l'OCAI après que la juridiction cantonale avait fixé le début du droit à la rente à une date antérieure; dès lors, le cas n'avait pu être liquidé immédiatement; par ailleurs, le sort du recours interjeté par l'assuré, devant le Tribunal fédéral des assurances, était de nature à influer sur le décompte du paiement de l'arriéré de rentes. L'Office fédéral des assurances sociales a renoncé à se déterminer.