Sachverhalt:
A.
Die Oberalpstrasse (Kantonsstrasse) ist Teil der Ost-/Westachse des schweizerischen Hauptstrassennetzes. Als Durchgangsstrasse dient sie unter anderem der Erschliessung der Surselva. Bei der Gemeinde Schluein entspricht sie den heutigen Anforderungen nicht mehr. So ist der Innerortsbereich stellenweise sehr eng und unübersichtlich. In einem schlechten Zustand sind die Schleuisertobelbrücke und die Unterführung "Haus Camenisch". Schliesslich ist die Einfahrt in die Oberalpstrasse beim Anschluss Sagogn in Richtung Laax (d.h. in östliche Richtung) heute nur unter Benutzung der Gegenfahrbahn möglich.
Die geplante Strassenkorrektion sieht daher in der Gemeinde Schluein zwischen Kilometer 18.50 und Kilometer 18.70 eine leicht angepasste Linienführung, eine Verbreiterung der Strasse sowie einen talseitigen Gehweg vor. Die Schleuisertobelbrücke und die Unterführung "Haus Camenisch" werden ersetzt. Schliesslich soll der Anschluss Sagogn neu gestaltet werden: Die heute spitzwinklige Einmündung der Via Veglia in die Oberalpstrasse soll so umgestaltet werden, dass ein rechtwinkliges Einmünden in die Hauptstrasse möglich ist. Dies bedingt eine Anpassung der kantonalen Verbindungsstrasse Via Veglia auf einer Strecke von rund 40 m sowie der Via Mulina auf einer Strecke von rund 50 m.
B.
Gegen das Strassenprojekt erhoben unter anderem A.A._ und B.A._ Einsprache. Diese sind Eigentümer der vom neuen Anschluss Sagogn beanspruchten Parzellen Nrn. 841 und 150; auf Parzelle Nr. 841 befindet sich der historische "Gasthof zur Post" (Baute Nr. 48).
Am 20. Mai 2014 hiess die Regierung des Kantons Graubünden das Auflageprojekt unter Auflagen gut und erteilte die spezialrechtlichen Bewilligungen. Die Einsprachen von A.A._ und B.A._ hiess sie teilweise gut (hinsichtlich Lärmschutz und Einfriedung des Vorgartens), überwies die Einsprachen hinsichtlich der geforderten Entschädigung an das Tiefbauamt Graubünden und wies die übrigen Einwände ab, soweit sie darauf eintrat.
C.
Dagegen erhoben A.A._ und B.A._ am 30. Juni 2014 Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Dieses führte am 16. November 2015 einen Augenschein durch und wies die Beschwerde am 17. November 2015 ab.
D.
Gegen den verwaltungsgerichtlichen Entscheid haben A.A._ und B.A._ am 10. Februar 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, die Entscheide des Verwaltungsgerichts und der Regierung seien aufzuheben und dem Auflageprojekt sei die Genehmigung zu verweigern, soweit es ihre Parzellen betreffe. Das Auflageprojekt sei innerorts so zu redimensionieren, dass die Parzelle Nr. 841 inklusive Vorgarten sowie die Parzelle Nr. 150 durch das Projekt nicht tangiert würden und der historische Strassenverlauf gewahrt werde. Eventualiter sei die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen.
E.
Das Verwaltungsgericht und die Regierung schliessen auf Abweisung der Beschwerde (soweit darauf einzutreten sei).
Das Bundesamt für Strassen (ASTRA) äussert sich als Bundesfachstelle für den Schutz historischer Verkehrswege (Art. 23 Abs. 1 lit. c der Verordnung über den Natur- und Heimatschutz vom 16. Januar 1991 [NHV; SR 451.1]) zum Eingriff in die Via Veglia, die als Wegabschnitt der alten linksrheinischen Kunststrasse von 1842, Objekt GR 71.7.2, als Objekt "historischer Verlauf mit Substanz" im Bundesinventar der historischen Verkehrswege der Schweiz (IVS) verzeichnet ist.
F.
Die Beschwerdeführer halten in ihrer Replik vom 13. Juni 2016 an ihren Anträgen fest.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid des Verwaltungsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG). Die Beschwerdeführer sind als vom Strassenprojekt betroffene Grundeigentümer zur Beschwerde legitimiert (<ref-law>). Auf die rechtzeitig erhobene Beschwerde (<ref-law>) ist daher einzutreten.
1.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundesrecht - einschliesslich Überschreitung oder Missbrauch des Ermessens - gerügt werden (<ref-law>). Das Bundesgericht wendet das Bundesrecht grundsätzlich von Amtes wegen an (<ref-law>). Die Verletzung von Grundrechten (einschliesslich die willkürliche Anwendung von kantonalem Recht) prüft es dagegen nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und genügend begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen).
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, sofern dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
1.2. Die Regierung hält die Vorbringen der Beschwerdeführer zu einer Alternativroute vom Ortszentrum von Schluein in Richtung Laax über den östlichen Zweig der Via Veglia (vgl. unten E. 2.2) für unzulässige Noven. Die Beschwerdeführer beantragen ihrerseits, die von der Regierung eingereichte Planungsstudie (Plan Nr. 19.4670.901, Planungsstudie AS H19 Sogn Pieder vom Februar 2016) sei als Novum aus dem Recht zu weisen.
Die Beschwerdeführer hatten schon in ihrer Einsprache ausdrücklich auf die erwähnte Alternativroute verwiesen, diese aber in ihrer Verwaltungsgerichtsbeschwerde nicht mehr erwähnt. Das Verwaltungsgericht prüfte die Variante dennoch, von Amtes wegen (E. 8c S. 13 f. des angefochtenen Entscheids), gestützt auf seine Feststellungen am Augenschein. Insofern gab der angefochtene Entscheid den Beschwerdeführern und dem Regierungsrat Anlass, sich zu dieser Alternative zu äussern; sie sind deshalb nach <ref-law> befugt, diesbezüglich neue Tatsachen und Beweismittel vorzubringen.
2.
Zunächst sind die Sachverhaltsrügen der Beschwerdeführer zu prüfen.
2.1. Das Verwaltungsgericht ging davon aus, dass ein rechtwinkliger Anschluss mit vollständiger Sicht auf beide Strassenrichtungen bezüglich Übersicht und damit auch bezüglich Sicherheit der heutigen spitzwinkligen Einfahrt deutlich überlegen sei. In etwas abgeschwächter Form gelte dies auch für die Doppelkurve vor dem Engnis der Häuser Nr. 48 (Gasthaus zur Post) und 49 (Sontga Clau) : Die Doppelkurve verlangsame den Verkehrsfluss und zwinge damit die Verkehrsteilnehmer zu grösserer Aufmerksamkeit; gefährliche Fahrmanöver unter Inanspruchnahme der Gegenfahrbahn zwecks besserer Sicht durch das Engnis würden damit unterbunden.
Die Beschwerdeführer halten das Gegenteil für richtig: Aufgrund der geplanten Doppelkurve würden die in Richtung Sagnogn fahrenden Verkehrsteilnehmer beinahe im rechten Winkel auf das Engnis zufahren. Dies zwinge sie in viel grösserem Ausmass als heute, die Gegenfahrbahn in Anspruch zu nehmen, um den Gegenverkehr zu sehen. Damit werde die Verkehrssicherheit nicht verbessert, sondern eine erhebliche Gefahr für den entgegenkommenden Verkehr wie auch für Fussgänger geschaffen.
Schon heute besteht ein Nadelöhr zwischen den Bauten Nrn. 48 und 49 mit beschränkten Sichtverhältnissen, dies offenbar mit der Folge, dass die von der Hauptstrasse in die Via Veglia einbiegenden Fahrzeuge die linke Fahrbahn benutzen, um entgegenkommende Autos rechtzeitig zu erkennen (so ausdrücklich der Rechtsvertreter der Beschwerdeführer am Augenschein, Protokoll S. 2). Insofern ändert sich die Situation also nicht wesentlich. Dagegen ist es nachvollziehbar, dass die heutige, fast gerade Ausfahrt Verkehrsteilnehmer aus Richtung Ilanz dazu verleiten kann, fast ungebremst auf den Engpass zuzufahren, während sie künftig, durch die Doppelkurve, schon vor dem Engnis zum Abbremsen gezwungen werden. Unter diesen Umständen ist es nicht offensichtlich unrichtig, aufgrund der Geschwindigkeitsreduktion insgesamt von einem Sicherheitsgewinn auszugehen.
Entscheidend war für das Verwaltungsgericht aber in erster Linie die Verbesserung von Sichtverhältnissen und Strassengeometrie für die von der Via Veglia in Richtung Laax auf die Kantonsstrasse einbiegenden Fahrzeuge, die heute (aufgrund der spitzwinkligen Kurve) die Gegenfahrbahn beanspruchen müssen. Diese Verbesserung ist offensichtlich; dies gilt auch dann, wenn die Einfahrt - wie die Beschwerdeführer geltend machen - nicht häufig genutzt wird.
2.2. Die Beschwerdeführer erheben sodann Sachverhaltsrügen zur bereits bestehenden Ausfahrt vom östlichen Zweig der Via Veglia in die Hauptstrasse nördlich der Kirche. Diese Ausfahrt werde schon heute benutzt; es treffe nicht zu, dass die Strasse oder die Abzweigung verbreitert werden müssten. Notfalls könne zur Verbesserung der Verkehrssicherheit die Geschwindigkeit auf der Kantonsstrasse bei der Einfahrt (heute: 80 km/h) herabgesetzt werden. Dies sei nicht abgeklärt worden.
Die Beschwerdeführer zeigen mit ihren Einwänden nicht auf, inwiefern die Feststellungen des Verwaltungsgerichts offensichtlich unrichtig sind. Dies gilt insbesondere hinsichtlich der bestehenden Abzweigung bei der Kirche (von der Via Sogn Pieder rechts auf die Via Veglia) : Das Verwaltungsgericht hielt fest, dass es für grössere, aus Sagogn kommende Fahrzeuge aufgrund des engen Kurvenradius nicht möglich sei, nach rechts auf die Via Veglia abzubiegen; eine Verbreiterung der Abzweigung sei jedoch aufgrund der vorhandenen historischen Bauten ausgeschlossen. Diese Feststellungen werden durch die von der Regierung eingereichte Planstudie mit Schleppkurven bestätigt. Daraus ergibt sich, dass die Abzweigung für grössere Fahrzeuge abgeflacht und erweitert werden müsste, was mit erheblichen Eingriffen an den dort befindlichen, denkmalgeschützten Bauten verbunden wäre.
Unter diesen Umständen durfte das Verwaltungsgericht diese Variante als weniger geeignete Massnahme qualifizieren, ohne weitere Abklärungen (z.B. zur Möglichkeit von Geschwindigkeitsbegrenzungen) vornehmen zu müssen.
2.3. Das Verwaltungsgericht hielt weiter fest, dass eine Sperrung oder Teilsperrung der Via de Laax (die von Sagogn aus in nördliche Richtung auf die Kantonsstrasse führt) absehbar sei, da sich diese in einem sanierungsbedürftigen Zustand befinde. Für eine gewisse Zeit sei daher mit einem nicht unerheblichen Mehrverkehr auf der Via Veglia zu rechnen, mit zahlreichen zusätzlichen Fahrten in Richtung Laax. Die streitige Neugestaltung der Einmündung werde gerade auch in dieser Phase zur Verkehrssicherheit beitragen.
Die Beschwerdeführer bringen dagegen zunächst vor, dass keine Anhaltspunkte für eine vollständige Sperrung der Via de Laax vorlägen; sie setzen sich aber nicht mit der vom Verwaltungsgericht ebenfalls erwähnten Teilsperrung auseinander. Soweit sie geltend machen, die neu geplante Verkehrsführung (Doppelkurve) stelle gerade für den Fall der Sperrung der Via da Laax eine erhebliche Verschlechterung der Verkehrssicherheit dar, kann auf das oben (E. 2.1) Gesagte verwiesen werden.
3.
Die Beschwerdeführer rügen weiter, die Regierung habe zu Unrecht auf die Einholung eines Gutachtens der Eidgenössischen Natur- und Heimatschutzkommission (ENHK) oder der Eidgenössischen Kommission für Denkmalpflege (EKD) verzichtet.
3.1. Die Einholung eines derartigen Gutachtens ist nach Art. 7 Abs. 2 des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451) vorgeschrieben, wenn bei der Erfüllung einer Bundesaufgabe (im Sinne von <ref-law>) ein Objekt, das in einem Inventar des Bundes nach Artikel 5 NHG aufgeführt ist, erheblich beeinträchtigt werden kann oder sich in diesem Zusammenhang grundsätzliche Fragen stellen. Ob dies der Fall ist, beurteilt die zuständige kantonale Fachstelle für den Natur-, Heimat- und Denkmalschutz (<ref-law>).
Vorliegend geht es um den Ausbau einer kantonalen Hauptstrasse. Da der Bund hierfür Beiträge entrichtet (<ref-law>), handelt es sich um eine Bundesaufgabe im Sinne von <ref-law>. Das Bauvorhaben betrifft einen nach Art. 3 der Verordnung über das Bundesinventar der historischen Verkehrswege der Schweiz vom 14. April 2010 (VIVS; SR 451.13) als Objekt "historischer Verlauf mit Substanz" klassierten Wegabschnitt der alten linksrheinischen Kunststrasse von 1942, Objekt GR 71.7.2. Streitig ist, ob der inventarisierte Abschnitt durch das Strassenprojekt erheblich beeinträchtigt werden kann oder sich in diesem Zusammenhang grundsätzliche Frage stellen.
3.2. Die kantonale Denkmalpflege und der Regierungsrat verneinten dies, nach Einholung einer Stellungnahme des Verantwortlichen Historische Verkehrswege beim ASTRA. Dieser hatte (mit E-Mail vom 10. März 2014) festgehalten, dass die ehemalige Linienführung der alten Oberlandstrasse durch die sukzessive Ausweitung der Verzweigung Kantonsstrasse - Via Veglia im Laufe der Zeit bereits überprägt und nur noch schwach ablesbar sei; zudem fehlten weitere erhaltenswerte bauliche Substanzelemente, weshalb das ASTRA dem Vorhaben zustimmen könne. Allerdings sei unbedingt darauf zu achten, dass der weitere Verlauf der alten Kunststrasse und insbesondere das Engnis zwischen den Häusern Nrn. 48 und 49 erhalten bleibe.
3.3. Vor Bundesgericht hält das ASTRA an dieser Einschätzung fest: Zwar würden durch das Strassenbauprojekt die ersten 30 m des Inventarobjekts, zwischen der Kantonsstrasse und den Bauten 48 und 49, in ihrer Linienführung und in ihrer Gesamterscheinung, vollständig umgestaltet. Allerdings weise der betroffene Strassenabschnitt keinerlei historische Bausubstanz mehr auf, wie sich sowohl aus der Geländekarte (http://ivs-gis.admin.ch_Legende_Zusatzinformationen zum Inventar_Grundlagen Wegelemente) als auch bei einer Verifizierung vor Ort zeige. Die Klassierung "historischer Verlauf mit Substanz" rühre von der noch ansatzweise ablesbaren ehemaligen Linienführung zwischen der Oberlandstrasse und den beiden Gebäuden her; ein weiteres Substanzelement finde sich in Form eines Mauerstücks östlich des Gebäudes Nr. 48. Diese Linienführung sei jedoch im Zuge der Strassenkorrektion in den 1950er Jahren besonders durch die Bildung einer neuen Verzweigung stark verändert worden. Das ASTRA erachtet daher die Neugestaltung der Abzweigung im Interesse der erhöhten Verkehrssicherheit und der strassenbaulich klareren Geometrie des Einmündungsbereichs als vertretbar. Der heutige Torcharakter der Gebäude 48 und 49 im Zusammenspiel mit dem historischen Verkehrsweg Via Veglia könne auch nach der Umgestaltung der Einmündung gewahrt werden. Dazu sei der Verlauf der Via Veglia, deren Proportionen sowie deren historische Bausubstanz (bergseitige Mauer) östlich der Gebäude 48 und 49 vollumfänglich zu erhalten. Die historische und ortsbildwichtige Torsituation sei nach der Bauausführung des Anschlussbereichs wiederherzustellen, indem die Vorgärten der Gebäude 48 und 49 analog der heutigen Situation und mit angepasster Materialisierung eingefriedet werden; für diese Arbeiten sei die Denkmalpflege Graubünden beizuziehen.
3.4. Gemäss <ref-law> (Schutzziele) sollen Objekte mit der Klassierung «historischer Verlauf mit viel Substanz» mit ihrer ganzen Substanz ungeschmälert erhalten werden (Abs. 1); Objekte mit der Klassierung «historischer Verlauf mit Substanz» sollen mit ihren wesentlichen Substanzelementen ungeschmälert erhalten werden (Abs. 2). Zur Substanz historischer Verkehrswege zählen gemäss <ref-law> namentlich der Verlauf der Wege, Strassen und Wasserwege im Gelände (Ziff. 1), Wegelemente, insbesondere Wegformen und -oberflächen sowie Wegbegrenzungen wie Böschungen, Mauern, Zäune und Alleen (Ziff. 2), Kunstbauten (Ziff. 3), Bautechniken und besonderes traditionelles Baumaterial (Ziff. 4) sowie Wegbegleiter wie Wegkreuze, Distanz- und Grenzsteine, Kapellen und andere mit dem Weg in einem funktionalen Zusammenhang stehende Bauten (Ziff. 5).
Die heutige Linienführung der Via Veglia im betroffenen Teil zwischen der Kantonsstrasse und den Häusern Nrn. 48 und 49 entspricht noch derjenigen der alten Oberlandstrasse, wie sich anhand der von "Swisstopo" aufgeschaltenen Landeskarten der Schweiz (1:50'000, Blattnummer 247 "Sardona", Datenstand 1957, 1966 und 1997) verifizieren lässt. Dagegen wurde die Via Veglia im fraglichen Teil bereits verbreitert, d.h. der heutige Verlauf im Gelände und die Wegbegrenzung (Einfriedungen der Vorgärten) entsprechen nicht mehr dem ursprünglichen Zustand; weitere historische Substanz ist unstreitig nicht vorhanden. Die Gesamterscheinung im Bereich der Abzweigung wurde durch den Bau der Kantonsstrasse Ende der 1950er Jahre und dem späteren Ausbau der Via Mulinas stark verändert. Insofern ist mit dem ASTRA davon auszugehen, dass die erneute Veränderung dieses Einmündungsbereichs die Schutzziele des Inventars nicht grundlegend in Frage stellt und deshalb als leichte Beeinträchtigung qualifiziert werden kann.
Voraussetzung ist allerdings, dass die restliche Strecke der Via Veglia und insbesondere die für den Abschnitt charakteristische "Torsituation" am Ortseingang von Schluein als wesentliches Substanzelement erhalten bleibt. Dies erscheint gewährleistet: Das Engnis zwischen den Häusern Nrn. 48 und 49 und der nachfolgende Teil der Via Veglia werden vom Projekt nicht verändert. Die für die Wegbegrenzung vor dem Engnis optisch wichtigen Einfriedungen der Vorgärten sollen nach den Bauarbeiten (angepasst an die neue Linienführung der Strasse und die Verkleinerung der Vorgärten) wiederhergestellt werden. Dies wird in der Detailplanung unter Mitwirkung der Denkmalpflege zu konkretisieren sein (vgl. in diesem Sinne die Auflagen Ziff. 1.2, 2.4 und 2.5 im Genehmigungsbeschluss).
Unter diesen Umständen war der Kanton nicht verpflichtet, ein Gutachten einer eidgenössischen Kommission einzuholen.
4.
Materiell beurteilt sich die Zulässigkeit des Eingriffs in das Inventarobjekt nach <ref-law>. Dessen Vorgaben werden für die historischen Verkehrswege in <ref-law> konkretisiert. Danach sind geringfügige Beeinträchtigungen der Schutzziele bei Erfüllung einer Bundesaufgabe nur zulässig, wenn sie sich durch ein Interesse rechtfertigen lassen, das gewichtiger ist als das Interesse am Schutz des Objekts (<ref-law>). Sind Eingriffe unter Abwägung aller Interessen unvermeidlich, so müssen sie sich auf ein Mindestmass beschränken (Abs. 5). Zum Ausgleich von Beeinträchtigungen sind Wiederherstellungsmassnahmen oder zumindest angemessene Ersatzmassnahmen, vorzugsweise am gleichen historischen Verkehrsweg, zu treffen.
4.1. Regierungsrat und Verwaltungsgericht haben dargelegt, dass die streitige neue Linienführung der Via Veglia ein gefahrloses Einbiegen in die stark befahrene Hauptstrasse für Verkehrsteilnehmer, insbesondere in Fahrtrichtung Laax, ermöglicht, und damit die Verkehrssicherheit gegenüber der heutigen Situation (spitzwinklige Einfahrt) deutlich verbessert wird. Die diesbezüglichen tatsächlichen Feststellungen der Vorinstanz sind nicht offensichtlich unrichtig (vgl. oben E. 2.1) und damit für das Bundesgericht bindend. Gleiches gilt für die Feststellungen des Verwaltungsgerichts zur mangelnden Tauglichkeit der von den Beschwerdeführern vorgebrachten Alternative (oben E. 2.2). Damit rechtfertigen wichtige öffentliche Interessen die geplante Umgestaltung der Einmündung, geht es doch um die Verhinderung von Unfällen mit Personenschäden.
4.2. Das Verwaltungsgericht hielt weiter fest, dass die von den Beschwerdeführern aufgeführten Geschwindigkeitsbegrenzungen das eigentliche Problem - die Beanspruchung der Gegenfahrbahn und die schlechten Sichtverhältnisse infolge ungenügender Geometrie - nicht beheben würden; ein Lichtsignal würde aufgrund des unterschiedlich starken Verkehrsflusses zu nicht gerechtfertigten Nachteilen (vermehrte Wartezeiten) im Verkehrsfluss auf der Kantonsstrasse führen.
Diese Erwägungen sind zutreffend; entgegen der Auffassung der Beschwerdeführer musste hierfür auch nicht zwingend die Beurteilung einer Fachstelle oder der Verkehrspolizei eingeholt werden, zumal sich das Verwaltungsgericht auf die Vernehmlassung der Regierung stützte, die auf den Sachverstand des fachkundigen Tiefbauamts zurückgreifen konnte. Damit erscheinen die beabsichtigten Eingriffe in den historischen Verkehrsweg unvermeidlich. Es wird Sache der Detailplanung sein, die Beeinträchtigung des Inventarobjekts und des Ortsbilds möglichst gering zu halten und die notwendigen Wiederherstellungs- oder Ersatzmassnahmen vorzusehen.
5.
Soweit die Beschwerdeführer eine Verletzung der Eigentumsgarantie (<ref-law>) geltend machen, kann auf die vorstehenden Erwägungen verwiesen werden. Die Verbesserung der Verkehrssicherheit ist ein überwiegendes öffentliches Interesse, das die Enteignung von Teilen der Vorgärten der Beschwerdeführer sowie die vorübergehende Beanspruchung ihrer Parzellen (einschliesslich des Vorplatzes des Hauses Nr. 48) während der Bauarbeiten rechtfertigt (<ref-law>). Die vorgesehenen Massnahmen erscheinen geeignet, erforderlich und verhältnismässig im engeren Sinne (<ref-law>).
6.
Damit ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (<ref-law>) und haben keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3.
Es werden keine Parteientschädigungen zugesprochen.
4.
Dieses Urteil wird den Parteien, der Regierung und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, sowie dem Bundesamt für Strassen schriftlich mitgeteilt.
Lausanne, 28. Juli 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Eusebio
Die Gerichtsschreiberin: Gerber