Faits :
A.
Le 8 juillet 2017, B._ et A._ ont informé le Conseil communal de U._ qu'ils renonçaient à contester une amende infligée pour avoir stationné un véhicule sur une "ancienne place rectangulaire à la fin de la route xxx", admettant contrevenir à l'interdiction signalée par un panneau (n o 2.50 de l'annexe 2 de l'ordonnance fédérale du 5 septembre 1979 sur la signalisation routière [OSR; RS 741.21]). Ils expliquaient cependant utiliser cet emplacement à cette fin depuis 1974; ils souhaitaient trouver un arrangement afin qu'eux-mêmes et leur fille puissent stationner leur véhicule à cet endroit lorsqu'ils se rendaient à leur chalet, situé à proximité.
Le 3 octobre 2017, le conseil communal a décidé de ne rien entreprendre de particulier dans le secteur; l'existence d'une servitude inscrite sur la place de rebroussement empêchait d'aménager plus d'une place de parc publique au sommet de la route xxx. Cette décision a été notifiée aux intéressés le 25 août 2017.
Le 2 novembre 2017, B._ et A._ ont prié le conseil communal de les informer de la date à laquelle avait été décidée la suppression de la place de stationnement et l'aménagement d'une aire de rebroussement à la fin de la route; ils l'invitaient par ailleurs à leur confirmer qu'une procédure de régularisation de cette signalisation serait prochainement ouverte.
En réponse, par courriel du 10 novembre 2017, la commune a indiqué que la Commission cantonale de signalisation routière (CCSR) avait fait paraître au Bulletin officiel du canton du Valais (B.O) du 5 janvier 1996 sa décision du 27 décembre 1995 autorisant la pose de signaux (n os 2.59.1 et 2.59.2) relatifs au début et à la fin d'une zone d'interdiction de stationner sur la route en question. Par ailleurs, à la suite d'une consultation publique publiée au B.O du 4 avril 2014, la CCSR avait approuvé un plan de signalisation comportant une interdiction de stationner à l'extrémité de cette même route; un extrait de plan a été communiqué à B._ et A._.
B.
Par acte du 27 novembre 2017, B._ et A._ ont recouru au Conseil d'Etat du canton du Valais; ils concluaient "préalablement" que la nullité de la signalisation interdisant le parcage, décidée en 1995 et l'"absence d'entrée en force de la nouvelle signalisation interdisant le parcage à l'extrémité de la route xxx" soient constatées. Principalement, ils demandaient l'annulation des décisions communales des 25 octobre et 10 novembre 2017; subsidiairement et en résumé, ils sollicitaient le maintien des places et la délivrance d'une autorisation de stationnement. A titre de mesures provisionnelles, B._ et A._ requéraient de pouvoir stationner à l'extrémité de la route jusqu'à droit connu sur leurs conclusions.
Le 5 septembre 2018, le Conseil d'Etat a rejeté la requête de mesures provisionnelles. Il précisait que l'assiette de la servitude à l'extrémité de la route ne pouvait être utilisée que comme place de rebroussement; l'intérêt privé des recourants à pouvoir stationner sur cette place devait céder le pas face à l'intérêt de la collectivité à faire respecter une interdiction de stationner de portée générale ayant été décidée à l'issue d'une "procédure complète et compréhensible pour chacun".
Le 18 septembre 2018, B._ et A._ ont recouru contre cette décision à la Cour de droit public du Tribunal cantonal du Valais. Par arrêt du 8 mai 2019, la cour cantonale a déclaré le recours irrecevable. En tant que décision incidente, le prononcé du 5 septembre 2018 ne pouvait faire l'objet d'un recours immédiat que pour autant qu'il soit de nature à causer un préjudice irréparable au sens de l'art. 42 al. 2 de la loi cantonale sur la procédure et la juridiction administratives du 6 octobre 1976 (LPJA; RS/VS 172.6), condition non réalisée en l'espèce.
C.
Agissant par les voies du recours en matière de droit public et du recours constitutionnel subsidiaire, B._ et A._ concluent principalement à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants. Subsidiairement, ils demandent au Tribunal fédéral de constater la violation par la cour cantonale du principe de célérité. Ils requièrent enfin, à titre de mesures provisionnelles, d'être autorisés à stationner à l'extrémité de la route xxx pour la durée de la procédure de recours.
Le Tribunal cantonal et la commune renoncent à se déterminer sur le recours. Le Conseil d'Etat conclut à son rejet.
Par ordonnance du 18 juillet 2019, le Président de la Ire Cour de droit public a admis la requête de mesures provisionnelles.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 116).
1.1. Le recours en matière de droit public a été déposé en temps utile (art. 100 LTF) et en la forme prévue (art. 42 LTF) à l'encontre d'un arrêt rendu par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF) statuant dans une cause de droit public (art. 82 let. a LTF). En tant que destinataires de l'arrêt attaqué, les intéressés ont la qualité pour recourir (art. 89 al. 1 LTF). Aucune des exceptions quant à l'objet du litige prévues par l'art. 83 LTF n'est par ailleurs réalisée.
La décision du 5 septembre 2018 par laquelle le Conseil d'Etat a rejeté la requête de mesures provisionnelles formée par les recourants est une décision incidente dès lors que l'effet de la mesure requise est limité à la durée du procès introduit par recours du 27 novembre 2017 (cf. <ref-ruling> consid. 1.1 p. 46 s.; arrêt 5A_857/2018 du 5 février 2019 consid. 3.1.1 et les arrêts cités). L'arrêt d'irrecevabilité du 8 mai 2019, qui trouve son origine dans un recours formé contre cette première décision incidente, revêt lui aussi - quoi qu'en disent les recourants - un caractère incident (cf. <ref-ruling> consid. 1.1 p. 382; arrêts 2C_1155/2016 du 3 avril 2017 consid. 1.2; 5A_878/2014 du 17 juin 2015 consid. 1.1, non publié in <ref-ruling>).
Dans ces conditions, le recours n'est en principe recevable que si l'arrêt attaqué est susceptible de causer un préjudice irréparable (art. 93 al. 1 let. a LTF) ou si son admission peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (let. b).
En l'occurrence, les recourants ne prétendent à juste titre pas que la condition de l'art. 93 al. 1 let. b LTF serait réalisée. Ils soutiennent en revanche que l'arrêt incident d'irrecevabilité, refusant de leur reconnaître le droit de recourir, équivaudrait, selon la jurisprudence, à un déni de justice formel, sur lequel il conviendrait d'entrer en matière, indépendamment de l'existence d'un préjudice irréparable. Il est toutefois douteux que cette exception s'applique en l'espèce: le recours ne porte en effet pas sur l'existence même d'un recours cantonal - cas de figure envisagé par la jurisprudence (cf. <ref-ruling> consid. 1.2 p. 346; arrêt 1B_415/2018 du 19 septembre 2018 consid. 2) -, mais sur la réalisation de l'une de ses conditions de recevabilité définie par le droit cantonal de procédure. Cette problématique peut quoi qu'il en soit demeurer indécise, le recours s'avérant mal fondé pour les motifs exposés ci-après.
1.2. Dès lors que la recevabilité du recours en matière de droit public - laissée indécise - n'est discutable que sous l'angle de l'existence d'un préjudice irréparable au sens de l'art. 93 al. 1 let. a LTF et non en lien avec l'objet de la décision attaquée (cf. art. 83 LTF), ou encore avec l'exigence d'une valeur litigieuse minimale (cf. art. 85 LTF), le recours constitutionnel subsidiaire est nécessairement irrecevable (art. 113 LTF; cf. JEAN-MAURICE FRÉSARD, Commentaire de la LTF, 2 e éd. 2014; n. 22 ss ad art. 113 LTF; voir également FLORENCE AUBRY GIRARDIN, Commentaire de la LTF précité, n. 15 ad art. 83 LTF).
2.
Selon l'art. 98 LTF, dans le cas des recours formés contre des décisions portant sur des mesures provisionnelles, seule peut être invoquée la violation des droits constitutionnels. Le Tribunal fédéral n'examine de tels griefs que s'ils ont été invoqués et motivés conformément au principe d'allégation (art. 106 al. 2 LTF). Dans ce contexte, il appartient à la partie recourante d'expliquer de manière claire et précise en quoi les principes constitutionnels sur lesquels elle se fonde auraient été violés; elle doit de même citer les dispositions du droit cantonal dont elle se prévaut et démontrer en quoi celles-ci auraient été appliquées arbitrairement (art. 9 Cst.; cf. <ref-ruling> consid. 2.8 p. 494; <ref-ruling> consid. 1.4).
3.
Invoquant une violation de leur droit d'être entendus et de l'art. 112 al. 1 let. b LTF, les recourants se plaignent d'un défaut de motivation de l'arrêt attaqué.
3.1. Le droit d'être entendu consacré à l'art. 29 al. 2 Cst. implique notamment l'obligation pour le juge de motiver sa décision, afin que le justiciable puisse la comprendre, la contester utilement s'il y a lieu et que l'autorité de recours puisse exercer son contrôle. Il suffit cependant, selon la jurisprudence, que le juge mentionne, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision. Il n'est cependant pas tenu de discuter tous les arguments soulevés par les parties, mais peut se limiter à ceux qu'il juge pertinents (<ref-ruling> consid. 4.3.2 p. 436; <ref-ruling> consid. 3.2.4 p. 41; <ref-ruling> consid. 2.2 p. 183).
Du droit d'être entendu, garanti par l'art. 29 al. 2 Cst., sont notamment déduites les exigences de motivation de l'art. 112 al. 1 let. b LTF, à teneur duquel les décisions qui peuvent faire l'objet d'un recours devant le Tribunal fédéral doivent contenir les motifs déterminants de fait et de droit (<ref-ruling> consid. 2.2 p. 84; arrêt 8C_221/2018 du 4 juillet 2019 consid. 6.2). Ainsi, lesdites décisions doivent indiquer clairement les faits qui sont établis et les déductions juridiques qui sont tirées de l'état de fait déterminant (BERNARD CORBOZ, Commentaire de la LTF, 2 e éd. 2014, n. 23 ad art. 112 LTF).
3.2. Les recourants estiment que l'arrêt attaqué ne contiendrait pas les faits pertinents nécessaires à la compréhension factuelle et juridique de cette décision. L'état de fait établi par l'instance précédente se limiterait à la "reprise des écrits échangés depuis le début de la procédure par les différentes parties, ainsi que la reformulation de leurs contenus", ce qui, à les suivre, serait insuffisant.
Tel qu'il est formulé, ce grief n'a toutefois pas de portée propre. En effet, il se confond avec les critiques liées à l'établissement lacunaire des faits, dont il sera question ci-après. S'agissant à proprement parler de la motivation adoptée par les Juges cantonaux, il ressort de l'arrêt attaqué que ceux-ci ont jugé que les inconvénients allégués par les recourants, à savoir le stationnement à plus de 30 minutes à pied de leur chalet, sur des places limitées à 1h30, ne résultaient pas de la décision entreprise, mais de la situation de leur parcelle: celle-ci ne bénéficie d'aucun droit de passage, de sorte que les recourants ne peuvent stationner leurs véhicules sur leur fonds et sont contraints d'opter pour des routes et parkings ouverts à l'usage commun. Sur cette base, la cour cantonale a estimé que les conditions d'un recours immédiat contre une décision incidente, définies par l'art. 41 al. 2 LPJA, n'étaient pas réalisées, le préjudice invoqué ne résultant pas du refus des mesures provisionnelles, mais de la situation et des caractéristiques de leur propriété. Quoi qu'en disent les recourants, cette motivation répond aux exigences de l'art. 29 al. 2 Cst. Elle leur permet de comprendre les motifs pour lesquels la cour cantonale a déclaré leur recours irrecevable, aspect qu'ils contestent d'ailleurs abondamment en lien avec leur grief d'application arbitraire de l'art. 41 al. 2 LPJA, discuté ultérieurement. Compte tenu de la motivation adoptée, on ne saurait, à ce stade, reprocher au Tribunal cantonal de n'avoir approfondi son instruction s'agissant de la situation de la parcelle des recourants et de la route xxx; la décision attaquée répond partant également aux réquisits de l'art. 112 al. 1 let. b LTF.
Mal fondé, le grief est rejeté.
4.
Les recourants se plaignent encore d'un établissement incomplet des faits. La cour cantonale aurait en substance ignoré une série d'éléments factuels, qui pourtant auraient dû la conduire à reconnaître l'existence d'un préjudice irréparable au sens de l'art. 41 al. 2 LPJA. Ce faisant, l'instance précédente se serait également livrée à une application arbitraire de cette disposition.
4.1.
4.1.1. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. Le recourant ne peut critiquer les constatations de fait ressortant de la décision attaquée que si celles-ci ont été effectuées en violation du droit au sens de l'art. 95 LTF ou de manière manifestement inexacte, c'est-à-dire arbitraire (<ref-ruling> consid. 6 p. 358), et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF; <ref-ruling> consid. 4.2 p. 234).
4.1.2. Aux termes de l'art. 41 LPJA, les décisions finales sont susceptibles de recours. Les décisions préjudicielles et incidentes sont attaquées conjointement avec la décision finale (al. 1). Les décisions préjudicielles ou incidentes pouvant causer un préjudice irréparable sont susceptibles d'un recours séparé (al. 2).
4.1.3. Appelé à revoir l'application faite d'une norme cantonale ou communale sous l'angle de l'arbitraire, le Tribunal fédéral ne s'écarte de la solution retenue que si celle-ci apparaît insoutenable ou en contradiction manifeste avec la situation effective, ou encore si elle a été adoptée sans motifs objectifs et en violation d'un droit certain. En outre, il ne suffit pas que les motifs de la décision critiquée soient insoutenables, encore faut-il que celle-ci soit arbitraire dans son résultat. Si l'application de la loi défendue par l'autorité cantonale ne se révèle pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation en cause, cette interprétation sera confirmée, même si une autre solution - éventuellement plus judicieuse - paraît possible (<ref-ruling> consid. 2.1 p. 168; <ref-ruling> consid. 4.3 p. 319; <ref-ruling> consid. 6.1 p. 379).
4.2. Selon la jurisprudence, il n'est en principe pas arbitraire d'interpréter la notion de préjudice irréparable prévue par le droit cantonal de procédure administrative à la lumière des principes applicables à l'art. 93 al. 1 let. a LTF (cf. arrêts 1C_88/2018 du 11 octobre 2018 consid. 2.2; 1C_317/2018 du 11 octobre 2018 consid. 2.2 publié in SJ 2019 I 151); les recourants le reconnaissent d'ailleurs expressément. Selon la jurisprudence rendue en application de l'art. 93 al. 1 let. a LTF, un préjudice irréparable n'est réalisé que lorsque la partie recourante subit un dommage qu'une décision favorable sur le fond ne fera pas disparaître complètement; il faut en outre qu'il s'agisse d'un inconvénient de nature juridique, un dommage économique ou de pur fait étant à cet égard insuffisant (<ref-ruling> consid. 1.2.1 p. 382; <ref-ruling> consid. 1.3.4; <ref-ruling> consid. 2.1 et consid. 2.2). La condition du préjudice irréparable, au sens de l'art. 93 al. 1 let. a LTF, s'apprécie par rapport à la décision de première instance, et non par rapport à la décision d'irrecevabilité du recours rendue par le tribunal supérieur (<ref-ruling> consid. 1.2 et les précédents cités).
4.3. Dans le détail, les recourants reprochent à l'instance précédente d'avoir ignoré que la route en cause est sans issue et que son extrémité aurait été constamment utilisée comme place de stationnement depuis 1970, utilisation autorisée, à tout le moins tolérée par l'autorité communale; ils font en outre valoir que la modification de la signalisation par zone est intervenue en 1996, mais n'aurait pas changé la situation s'agissant de l'admission du stationnement à l'extrémité de la route. Les recourants se prévalent encore d'une procédure de régularisation menée en 2014, qui en réalité ne concernerait pas la route en cause. L'arrêt cantonal tairait par ailleurs qu'aucun panneau d'interdiction n'aurait été installé sur le site avant 2017, date à laquelle l'autorité communale aurait modifié la signalisation hors de toute procédure. La cour cantonale aurait enfin omis d'instruire, respectivement de retenir que les recourants n'avaient aucune autre possibilité de parcage pour accéder à leur chalet, dès lors qu'il n'existerait pas de parking public dans le secteur de xxz, que le plus proche se situerait à plusieurs kilomètres, soit à 30 minutes à pied et que sa durée d'utilisation serait limitée dans le temps.
Les recourants déduisent de ces éléments l'existence d'un préjudice irréparable ainsi qu'une atteinte à leur droit de propriété. Ils soutiennent que la cour cantonale aurait à tort considéré que ce préjudice trouvait sa cause dans la situation de leur parcelle et non "dans les modifications intervenues en 2017 qui font l'objet de la procédure au fond". En outre, si le droit de continuer à stationner à l'extrémité de la route xxx devait être reconnu, le préjudice subi, le temps de la procédure au fond, ne pourrait être réparé.
Ce faisant, les recourants n'expliquent cependant pas en quoi le préjudice dont ils excipent revêtirait un caractère irréparable au sens de l'art. 41 al. 2 LPJA, respectivement de la jurisprudence rendue en application de l'art. 93 al. 1 let. a LTF. Les faits dont ils se prévalent - dont la recevabilité peut demeurer indécise - relèvent en réalité, pour l'essentiel, de la procédure au fond et non de la question de l'existence d'un préjudice irréparable lié au refus des mesures provisionnelles. Les recourants se méprennent de surcroît lorsqu'ils voient dans l'interdiction de stationner une violation de leur droit de propriété (art. 26 Cst.) : ils perdent de vue que l'interdiction litigieuse, outre qu'elle est d'ordre général, s'avère indépendante de leur parcelle puisqu'elle concerne le domaine public, voire la propriété d'un tiers grevée d'une servitude; la substance de leur droit de propriété ne s'en trouve pas atteinte et l'on ne voit pas en quoi l'utilisation de leur chalet serait restreinte durant la procédure. Les inconvénients liés au fait - fût-il établi - de devoir stationner à 30 minutes à pied du chalet, sur des places à durée restreinte, outre qu'ils relèvent du pur fait, n'entraînent à première vue pas des modifications organisationnelles s'agissant de l'accès au chalet, sur lesquelles on ne pourrait revenir ultérieurement; les recourants n'exposent d'ailleurs rien de tel. Il s'ensuit qu'il n'est pas arbitraire, à tout le moins dans le résultat, d'avoir nié l'existence d'un préjudice irréparable au sens de l'art. 41 al. 2 LPJA.
Le grief est partant rejeté dans la mesure où il est recevable.
5.
Les recourants se plaignent encore d'une violation du principe de la célérité garanti par l'art. 29 al. 1 Cst. Dans ce cadre, ils se prévalent également d'une application arbitraire de l'art. 61a LPJA, qui, en substance, impartit à l'autorité un délai de six mois, à compter du dépôt du recours, pour statuer. Les recourants reconnaissent cependant qu'il s'agit d'un délai d'ordre; ils n'exposent par ailleurs pas en quoi cette disposition aurait fait l'objet d'une application arbitraire ni ne prétendent qu'elle leur conférerait des garanties plus étendues que l'art. 29 al. 1 Cst. En conséquence, le présent grief sera exclusivement examiné sous ce dernier angle (art. 106 al. 2 LTF).
5.1. Dans une procédure judiciaire ou administrative, l'art. 29 al. 1 Cst. garantit notamment le droit à toute personne que sa cause soit traitée dans un délai raisonnable. Cette disposition consacre le principe de célérité ou, en d'autres termes, prohibe le retard injustifié à statuer. L'autorité viole cette garantie constitutionnelle lorsqu'elle ne rend pas la décision qu'il lui incombe de prendre dans le délai prescrit par la loi ou dans un délai que la nature de l'affaire ainsi que toutes les autres circonstances font apparaître comme raisonnable. Le caractère raisonnable du délai s'apprécie selon les circonstances particulières de la cause, eu égard notamment à la complexité de l'affaire, à l'enjeu du litige pour l'intéressé, à son comportement ainsi qu'à celui des autorités compétentes (<ref-ruling> consid. 1.3.1 p. 377). Selon la jurisprudence, en présence d'une décision de nature provisionnelle, le respect du principe de célérité doit faire l'objet d'une attention particulière (cf. arrêt 1C_154/2018 du 4 juillet 2018 consid. 7 non publié in JdT 2018 I 309).
5.2. En l'occurrence, le recours de droit administratif, assorti d'une requête de mesures préprovisionnelles et provisionnelles a été déposé le 18 septembre 2018. Le 3 octobre 2018, le Conseil d'Etat a informé l'instance précédente qu'il renonçait à se déterminer sur la requête préprovisionnelle. La commune s'est pour sa part exprimée en défaveur de cette requête, le 4 octobre 2018. A la suite de ces écritures, le Tribunal cantonal a statué sans délai, rejetant la requête de mesures provisionnelles - et par voie de conséquence la requête préprovisionnelle - par décision incidente du 12 octobre 2018. Par ailleurs, à teneur du dossier cantonal, il apparaît qu'en dépit de la prétendue "atteinte considérable [à leur] droit de la propriété" dont se plaignent les recourants, ceux-ci ne se sont manifestés que le 29 avril 2019 pour solliciter qu'un jugement soit rendu à brève échéance, ce dont il convient également de tenir compte, selon la jurisprudence (cf. <ref-ruling> consid. 5.2 p. 332; arrêt 2C_553/2017 du 30 juin 2017 consid. 5). Or, l'arrêt entrepris a été rendu moins de 10 jours après cette interpellation, le 8 mai 2019, soit environ cinq mois après la fin du dernier échange d'écritures. Dans ces conditions, au regard de la nature de la cause et même s'il faut concéder aux recourants que celle-ci ne présentait pas de difficulté particulière, en statuant d'emblée sur les conclusions provisionnelles et en rendant l'arrêt attaqué un peu plus de sept mois après le dépôt du recours, le Tribunal cantonal n'a pas violé le principe de célérité.
Mal fondé, le grief est rejeté.
6.
Sur le vu de ce qui précède, le recours constitutionnel subsidiaire doit être déclaré irrecevable. Le recours en matière de droit public est quant à lui rejeté, dans la mesure de sa recevabilité. Les frais judiciaires sont mis à la charge solidaire des recourants, qui succombent à ce stade (art. 66 al. 1 et al. 5 LTF). Il n'est pas alloué de dépens (art. 68 al. 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours constitutionnel subsidiaire est irrecevable.
2.
Le recours en matière de droit public est rejeté dans la mesure où il est recevable.
3.
Les frais de justice, arrêtés à 3'000 fr., sont mis à la charge des recourants, solidairement entre eux.
4.
Il n'est pas alloué de dépens.
5.
Le présent arrêt est communiqué aux mandataires des recourants et de la Commune de U._, au Conseil d'Etat du canton du Valais ainsi qu'au Tribunal cantonal du canton du Valais.
Lausanne, le 2 septembre 2019
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Chaix
Le Greffier : Alvarez