A.- Par décision du 23 juillet 1997, l'Office de l'as-
surance-invalidité du canton du Valais (ci-après : l'offi-
ce) a alloué une rente entière d'invalidité à M._
dès le 1er juin 1997, au motif que celui-ci était totale-
ment invalide en raison de ses troubles psychiques. Par
jugement du 6 janvier 1998, le Tribunal cantonal des assu-
rances du canton du Valais a rejeté le recours formé par
l'assuré contre cette décision. Par arrêt du 24 février
1999, le Tribunal fédéral des assurances a annulé ce juge-
ment et renvoyé la cause à la juridiction cantonale pour un
complément d'instruction sur la question de la date de la
détérioration de l'état de santé de l'assuré.
B.- La Cour cantonale a requis un nouveau rapport du
docteur A._, interniste et spécialiste en rhuma-
tologie. Dans une lettre du 29 avril 1999, ce médecin a
soutenu que la première manifestation objective de péjo-
ration de l'état psychique de son patient remontait au
3 avril 1989. De son côté, la doctoresse Z._,
médecin adjoint aux institutions psychiatriques Y._,
a déclaré que l'incapacité de travail totale de l'assuré
remontait au mois de septembre 1994 (lettre du 14 juin
1999).
Par jugement du 25 juin 1999, l'autorité cantonale a
mis M._ au bénéfice d'une rente entière d'invalidité
dès le 1er septembre 1995. Elle a considéré en bref que le
rapport du 14 juin 1999 de la doctoresse Z._ était
le seul qui permettait de fixer la date de l'aggravation de
l'état de santé de l'assuré.
C.- M._ et l'office interjettent recours de
droit administratif contre ce jugement dont ils demandent
l'un et l'autre l'annulation. Le premier nommé conclut à
l'octroi d'une rente d'invalidité dès le 1er janvier 1988.
Il fait valoir qu'il subit une incapacité totale et irré-
versible de travail depuis cette date. L'office conclut au
rejet du recours de l'assuré et implicitement au renvoi de
la cause pour un complément d'instruction. Il soutient, en
particulier, que le bref rapport du 14 juin 1999 de la doc-
toresse Z._, sur lequel les premiers juges ont fondé
leur appréciation, n'a pas de caractère probant.
L'assuré sollicite également le bénéfice de l'assistance
judiciaire. L'office fédéral des assurances sociales
propose l'admission du recours de l'office.
Considérant en droit
:
1.- Les recours de droit administratif concernent des
faits de même nature, portent sur des questions juridiques
communes et sont dirigés contre le même jugement, de sorte
qu'il se justifie de les réunir et de les liquider dans un
seul arrêt (<ref-ruling> consid. 1, 120 V 466 consid. 1 et
les références; Poudret, Commentaire de la loi fédérale
d'organisation judiciaire, vol. I, p. 343 s.).
2.- a) Aux termes de l'art. 29 al. 2 Cst, en vigueur
depuis le 1er janvier 2000, les parties ont le droit d'être
entendues. Dans un arrêt non publié I. du 9 mai 2000
(I 278/99, consid. 1a/aa), le Tribunal fédéral des assu-
rances a constaté que la disposition précitée n'imposait
aucune modification de la jurisprudence rendue sous l'em-
pire de l'ancienne constitution en la matière. La juris-
prudence a déduit du droit d'être entendu, en particulier,
le droit pour le justiciable de s'expliquer avant qu'une
décision ne soit prise à son détriment, celui de fournir
des preuves quant aux faits de nature à influer sur le sort
de la décision, celui d'avoir accès au dossier, celui de
participer à l'administration des preuves, d'en prendre
connaissance et de se déterminer à leur propos (ATF
124 V 181 consid. 1a et 375 consid. 3b et les références).
Une condition nécessaire du droit de consulter le dossier
est que l'autorité, lorsqu'elle verse au dossier de nouvel-
les pièces dont elle entend se prévaloir dans son jugement,
soit tenue d'en aviser les parties (<ref-ruling> con-
sid. 2b, 114 Ia 100 consid. 2c et les références). Encore
qu'elle ne soit pas obligée de les renseigner sur chaque
production de pièces, car il suffit qu'elle tienne le dos-
sier à leur disposition (<ref-ruling> consid. 2a et les
références; RCC 1991 p. 107 consid. 4a). Le droit d'être
entendu est une garantie constitutionnelle de caractère
formel, dont la violation doit entraîner l'annulation de la
décision attaquée, indépendamment des chances de succès du
recourant sur le fond (<ref-ruling> consid. 4a et les
arrêts cités). L'autorité peut, certes, refuser la consul-
tation de pièces à certaines conditions (cf. <ref-law>).
Toutefois une pièce dont la consultation a été refusée à la
partie ne peut être utilisée à son désavantage que si l'au-
torité lui en a communiqué, oralement ou par écrit, le con-
tenu essentiel se rapportant à l'affaire et lui a donné en
outre l'occasion de s'exprimer et de fournir des contre-
preuves (<ref-law>).
b) En l'occurrence, les résultats de l'instruction
complémentaire ordonnée par les premiers juges à la suite
de l'arrêt du Tribunal fédéral des assurances du 24 février
1999 n'ont pas été communiqué aux parties. Celles-ci n'en
ont eu connaissance qu'à la lecture du jugement attaqué. Il
s'agit là d'une violation des règles essentielles de procé-
dure qu'il y a lieu de relever d'office (art. 105 al. 2 et
132 OJ). Compte tenu de sa gravité, cette violation ne
saurait être réparée devant la Cour de céans malgré le
plein pouvoir d'examen dont elle dispose. Au demeurant, la
réparation d'un tel vice ne doit avoir lieu qu'exception-
nellement (<ref-ruling> consid. 4a et les références. Le
jugement entrepris doit dès lors être annulé pour ce pre-
mier motif.
3.- a) Selon l'<ref-law>, l'invalidité est
réputée survenue dès qu'elle est, par sa nature et sa
gravité, propre à ouvrir droit aux prestations entrant en
considération. Ce moment doit être déterminé objectivement,
d'après l'état de santé; des facteurs externes fortuits
n'ont pas d'importance. Il ne dépend en particulier ni de
la date à laquelle une demande a été présentée, ni de celle
à partir de laquelle une prestation a été requise, et ne
coïncide pas non plus nécessairement avec le moment où
l'assuré apprend, pour la première fois, que l'atteinte à
sa santé peut ouvrir droit à des prestations d'assurance
(<ref-ruling> consid. 3a et les références). Selon
l'<ref-law>, le droit à la rente au sens de
l'<ref-law> prend naissance au plus tôt à la date à
partir de laquelle l'assuré présente une incapacité de gain
durable de 40 pour cent au moins (let. a) ou à partir de
laquelle il a présenté, en moyenne, une incapacité de
travail de 40 pour cent au moins pendant une année sans
interruption notable (let. b).
b) En l'espèce, il ressort du complément d'instruction
auquel ont procédé les premiers juges que le docteur
A._ fixe le début de la péjoration de l'état
psychique de son patient au 3 avril 1989. De son côté, la
doctoresse Z._ date l'aggravation de l'état de santé
de l'assuré du 26 septembre 1994, moment auquel il a inter-
rompu son stage de réadaptation aux Ateliers X._.
Or, d'une part, ces médecins sont en désaccord quant à la
date de la survenance de l'aggravation de l'état de santé
de l'assuré. D'autre part, la doctoresse Z._ avait
indiqué, dans un rapport du 16 mai 1997, que le syndrome
douloureux somatoforme persistant décrit par le docteur
C._ en juillet 1995 s'était compliqué de modifi-
cations durables de la personnalité et d'un état dépressif,
laissant ainsi entendre que l'aggravation de l'état de
santé psychique de l'assuré était postérieure au mois de
juillet 1995. En outre, c'est seulement en été 1995 que le
docteur A._ est intervenu auprès du docteur
C._, psychiatre, pour que celui-ci examine l'assuré.
Il résulte de ce qui précède qu'il n'est pas possible à la
lumière des documents médicaux au dossier de trancher en
connaissance de cause la question de la naissance du droit
à la rente de l'assuré. Dans ces conditions, une expertise
psychiatrique judiciaire est indispensable pour déterminer
depuis quand l'atteinte à la santé psychique dont souffre
l'assuré entraîne une incapacité de gain.
Il faut rappeler à cet égard que dans un arrêt récent
(cf. VSI 2000 p. 152) le Tribunal fédéral des assurances,
se fondant principalement sur une étude de Mosimann (Soma-
toforme Störungen : Gerichte und (psychiatrische) Gutach-
ten, RSAS 1999, p. 1 ss et 105 ss) a défini la tâche du
médecin ou de l'expert, lorsque celui-ci doit se prononcer
sur le caractère invalidant de troubles somatoformes. Sur
le plan psychiatrique, l'expert doit poser un diagnostic
dans le cadre d'une classification reconnue et se prononcer
sur le degré de gravité de l'affection. Il doit évaluer le
caractère exigible de la reprise par l'assuré d'une acti-
vité lucrative. Ce pronostic tiendra compte de divers
critères, tels une structure de la personnalité présentant
des traits prémorbides, une comorbidité psychiatrique, des
affections corporelles chroniques, une perte d'intégration
sociale, un éventuel profit tiré de la maladie, le caractè-
re chronique de celle-ci sans rémission durable, une durée
de plusieurs années de la maladie avec des symptômes sta-
bles ou en évolution, l'échec de traitements conformes aux
règles de l'art. Le cumul des critères précités fonde un
pronostic défavorable. Enfin, le médecin ou l'expert doit
s'exprimer sur le cadre psychosocial de la personne exami-
née. Au demeurant, la recommandation de refus d'une rente
doit également reposer sur différents critères. Au nombre
de ceux-ci figurent la divergence entre les douleurs décri-
tes et le comportement observé, l'allégation d'intenses
douleurs dont les caractéristiques demeurent vagues, l'ab-
sence de demande de soins, les grandes divergences entre
les informations fournies par le patient et celles ressor-
tant de l'anamnèse, le fait que des plaintes très démons-
tratives laissent insensible l'expert, ainsi que l'alléga-
tion de lourds handicaps malgré un environnement psychoso-
cial intact.
Sur le vu de ce qui précède, les recours se révèlent
tous deux bien fondés et le jugement entrepris doit être
annulé, la cause étant derechef renvoyée à l'autorité can-
tonale pour instruction complémentaire.
4.- S'agissant d'un litige qui concerne l'octroi ou le
refus de prestations d'assurance, la procédure est gratuite
(art. 134 OJ). Dans cette mesure, la requête de M._
tendant à l'octroi de l'assistance judiciaire gratuite est
sans objet.
Elle doit par ailleurs être rejetée dans la mesure où
elle tend à la prise en charge de dépens. En effet, l'as-
suré n'est pas représenté par un avocat ou une autre per-
sonne qualifiée et ne remplit pas les conditions exception-
nelles dans lesquelles des dépens peuvent être alloués en
pareil cas (cf. <ref-ruling>).


Par ces motifs, le Tribunal fédéral des assurances
p r o n o n c e
:
I. Le recours de M._ est admis.
II. Le recours de l'Office cantonal de l'assurance-inva-
lidité du canton du Valais est admis.
III. Le jugement du Tribunal cantonal des assurances du
canton du Valais du 25 juin 1999 est annulé, la cause
étant renvoyée à cette autorité pour complément
d'instruction au sens des considérants et nouveau
jugement.
IV. Il n'est pas perçu de frais de justice.
V. La demande d'assistance judiciaire de M._ est
rejetée.
VI. Le présent arrêt sera communiqué aux parties, au Tri-
bunal cantonal des assurances du canton du Valais et à
l'Office fédéral des assurances sociales.
Lucerne, le 29 mai 2000
Au nom du
Tribunal fédéral des assurances
Le Président de la IIIe Chambre :
p. le Greffier :