Faits : A. B._ est propriétaire de la parcelle n o 2214 du cadastre de la Commune de Chalais, au lieu-dit "Coujon", à Vercorin. Au cours de l'hiver 2005-2006, un couvert à bois ouvert sur trois côtés et occupant la partie est de cette parcelle s'est écroulé sous le poids de la neige. Le 28 avril 2006, A._, époux de B._, a demandé à la Commune de Chalais l'autorisation de reconstruire ledit couvert; des plans ont été déposés le 10 mai 2006. Le Conseil communal de Chalais a donné son aval le 20 mai 2006, soulignant que le couvert devait "absolument" être refait "dans le gabarit de l'ancien". Lors d'un contrôle du 7 août 2006, il a été constaté que la nouvelle construction présentait des dimensions différentes de l'ouvrage antérieur. La commune a en conséquence ordonné sa remise en état. A._ a sollicité la reconsidération de cette décision. L'administration communale a en conséquence publié la demande de reconstruction au Bulletin officiel du canton du Valais (BO) du 8 septembre 2006, en signalant une dérogation à la distance à la limite; celle-ci concernait la limite avec le fonds n o 2211, voisin à l'est. Dans le cadre de cette enquête, les époux C._, propriétaires de la parcelle n o 2211 ont formé opposition. Le 16 novembre 2006, le conseil communal est revenu sur l'ordre de remise en état et a autorisé a posteriori l'ouvrage tel que reconstruit; il a également rejeté l'opposition des voisins. Les décisions rendues par la commune ont suscité différentes procédures judiciaires. A ainsi notamment fait l'objet d'un recours au Conseil d'Etat du canton du Valais l'autorisation de construire délivrée le 16 novembre 2006, lequel a été admis le 4 mai 2011; le permis de construire a été annulé et la cause renvoyée à l'administration communale pour nouvelle décision. Par arrêt du 21 octobre 2011, le Tribunal cantonal a confirmé la décision du Conseil d'Etat. La cour cantonale retenait notamment que les droits acquis de A._ et B._ liés à la construction de longue date d'un abri en bois sur la parcelle n o 2214, reconnus par le Conseil d'Etat, n'avaient pas été remis en question. Elle a par ailleurs jugé que le nouvel ouvrage pouvait dépasser les dimensions de l'ancien abri dans une certaine mesure: pour des motifs tirés du principe de la bonne foi, seules demeuraient encore en cause les dimensions de la nouvelle construction excédant celles figurant sur les plans déposés le 10 mai 2006 et validés par la commune; une hauteur du couvert de 2,84 m était ainsi protégée; faute d'indication, la largeur était régie par les droits acquis découlant des dimensions de l'ancien couvert (3,82 m selon les estimations du Conseil d'Etat, dans sa décision du 4 mai 2011). B. Par décision du 18 septembre 2012, après avoir repris l'instruction de la cause, le Conseil communal de Chalais a ordonné la "réduction de la surhauteur du couvert de 15 cm, dans un délai de 3 mois". A._ et B._ ont recouru contre cette décision au Conseil d'Etat, concluant à son annulation. Les époux C._ en ont fait de même, demandant, pour leur part, la démolition de l'ouvrage. Par décision du 21 juin 2017, le Conseil d'Etat a rejeté les recours. Les époux C._ se sont pourvus contre cette décision devant le Tribunal cantonal, maintenant leurs conclusions en démolition. Les époux A._ ont également recouru à la cour cantonale, concluant principalement à l'annulation de l'ordre de démolition. Après avoir joint les causes, le Tribunal cantonal a, par arrêt du 31 janvier 2018, rejeté le recours de A._ et B._. Il a en revanche partiellement admis le pourvoi formé par les époux C._. La cour cantonale a en substance considéré que l'étendue des droits acquis dont pouvaient se prévaloir les époux A._ et B._ avait été établie de façon définitive par la décision du Conseil d'Etat du 4 mai 2011, confirmée par l'arrêt du Tribunal cantonal du 21 octobre 2011. Il convenait dès lors de ramener le couvert à une hauteur ne dépassant pas 2,84 m ainsi qu'à une largeur d'au plus 3,82 m. C. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent principalement au Tribunal fédéral d'annuler l'arrêt attaqué ainsi que l'ordre de remise en état du 18 septembre 2012. Subsidiairement, ils concluent au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants. Ils sollicitent également l'octroi de l'effet suspensif. Le Tribunal cantonal renonce à se déterminer. Le Conseil d'Etat se réfère à l'arrêt attaqué et conclut au rejet du recours. La Commune de Chalais s'en remet à la décision du Tribunal fédéral. Les intimés concluent en substance à l'annulation de l'arrêt attaqué, au renvoi de la cause à l'instance précédente pour un nouvel établissement des faits et pour ordonner principalement le respect des dimensions de l'ancienne construction et, subsidiairement, la démolition du couvert litigieux. Aux termes d'un ultime échange d'écritures, les parties persistent dans leurs conclusions respectives. Par ordonnance du 27 mars 2018, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif. Par ordonnance du 28 novembre 2018, à la demande des parties, la cause a été suspendue jusqu'au 28 mai 2019 afin de leur permettre d'aboutir à un éventuel accord. Faute pour celles-ci de s'être prononcées dans le délai imparti, la procédure de recours a été reprise par ordonnance du 6 juin 2019.