Sachverhalt: Sachverhalt: A. Der Vertrag zwischen der Schweizerischen Eidgenossenschaft und dem Grossherzogtum Baden betreffend die Weiterführung der badischen Eisenbahnen über schweizerisches Gebiet vom 27. Juli 1852 räumt der deutschen Seite das Recht ein, über schweizerisches Gebiet eine Verbindungsstrasse (Zollfreie Strasse) zwischen den Städten Lörrach und Weil am Rhein zu bauen. Ein vom Regierungspräsidium Freiburg im Breisgau ausgearbeitetes "Auflageprojekt vom November 1974" wurde öffentlich aufgelegt und in der Folge aufgrund von Einsprachen überarbeitet. Der Regierungsrat des Kantons Basel-Stadt genehmigte am 16. Dezember 1975 das überarbeitete Projekt mit verschiedenen Auflagen und Bedingungen. Am 7. Mai 1976 trafen das Land Baden-Württemberg und der Kanton Basel-Stadt eine Vereinbarung über die technischen Einzelheiten im Zusammenhang mit dem Bau, Betrieb und Unterhalt der Verbindungsstrasse. In der Folge schlossen die Schweizerische Eidgenossenschaft und die Bundesrepublik Deutschland am 25. April 1977 einen Staatsvertrag über die Verbindungsstrasse ab (SR 0.725.122). Gemäss diesem bestimmen sich Linienführung und Bau der Strasse nach dem vom Regierungsrat des Kantons Basel-Stadt genehmigten Auflageprojekt, wobei auf einen dem Vertrag beigefügten "Rahmenplan" verwiesen wird (Art. 2). Der Staatsvertrag ist am 14. Dezember 1979 von der Bundesversammlung ratifiziert worden und am 1. August 1980 in Kraft getreten. A. Der Vertrag zwischen der Schweizerischen Eidgenossenschaft und dem Grossherzogtum Baden betreffend die Weiterführung der badischen Eisenbahnen über schweizerisches Gebiet vom 27. Juli 1852 räumt der deutschen Seite das Recht ein, über schweizerisches Gebiet eine Verbindungsstrasse (Zollfreie Strasse) zwischen den Städten Lörrach und Weil am Rhein zu bauen. Ein vom Regierungspräsidium Freiburg im Breisgau ausgearbeitetes "Auflageprojekt vom November 1974" wurde öffentlich aufgelegt und in der Folge aufgrund von Einsprachen überarbeitet. Der Regierungsrat des Kantons Basel-Stadt genehmigte am 16. Dezember 1975 das überarbeitete Projekt mit verschiedenen Auflagen und Bedingungen. Am 7. Mai 1976 trafen das Land Baden-Württemberg und der Kanton Basel-Stadt eine Vereinbarung über die technischen Einzelheiten im Zusammenhang mit dem Bau, Betrieb und Unterhalt der Verbindungsstrasse. In der Folge schlossen die Schweizerische Eidgenossenschaft und die Bundesrepublik Deutschland am 25. April 1977 einen Staatsvertrag über die Verbindungsstrasse ab (SR 0.725.122). Gemäss diesem bestimmen sich Linienführung und Bau der Strasse nach dem vom Regierungsrat des Kantons Basel-Stadt genehmigten Auflageprojekt, wobei auf einen dem Vertrag beigefügten "Rahmenplan" verwiesen wird (Art. 2). Der Staatsvertrag ist am 14. Dezember 1979 von der Bundesversammlung ratifiziert worden und am 1. August 1980 in Kraft getreten. B. Mit Beschluss vom 4. April 1995 erteilte der Regierungsrat des Kantons Basel-Stadt dem Regierungspräsidium Freiburg im Breisgau eine auf fünf Jahre befristete Bewilligung zur Rodung von 2090 m2 Wald in Riehen auf den Parzellen Nrn. A013600 und A013700 zum Bau der Zollfreien Strasse. Das Bundesgericht wies die dagegen eingereichten Beschwerden ab und hielt fest, der Staatsvertrag regle abschliessend, unter welchen Voraussetzungen der Vertragszweck erreicht werden solle (BGE 122 II 234 E. 4b-d S. 237 f.). Die Verwirklichung der Verbindungsstrasse solle nicht vom Ergebnis nachfolgender landesinterner Bewilligungsverfahren abhängen. Die bewilligte Rodung verletze weder Art. 5 des Bundesgesetzes über den Wald vom 4. Oktober 1991 (WaG; SR 921.0) noch Koordinationsgrundsätze (a.a.O., E. 4e S. 240). B. Mit Beschluss vom 4. April 1995 erteilte der Regierungsrat des Kantons Basel-Stadt dem Regierungspräsidium Freiburg im Breisgau eine auf fünf Jahre befristete Bewilligung zur Rodung von 2090 m2 Wald in Riehen auf den Parzellen Nrn. A013600 und A013700 zum Bau der Zollfreien Strasse. Das Bundesgericht wies die dagegen eingereichten Beschwerden ab und hielt fest, der Staatsvertrag regle abschliessend, unter welchen Voraussetzungen der Vertragszweck erreicht werden solle (BGE 122 II 234 E. 4b-d S. 237 f.). Die Verwirklichung der Verbindungsstrasse solle nicht vom Ergebnis nachfolgender landesinterner Bewilligungsverfahren abhängen. Die bewilligte Rodung verletze weder Art. 5 des Bundesgesetzes über den Wald vom 4. Oktober 1991 (WaG; SR 921.0) noch Koordinationsgrundsätze (a.a.O., E. 4e S. 240). C. Wegen Verzögerungen im Baubewilligungsverfahren drohte die auf den 26. Juni 2001 befristete Rodungsbewilligung unbenutzt abzulaufen. Auf Gesuch des Regierungspräsidiums Freiburg hin, verlängerte der Regierungsrat des Kantons Basel-Stadt die Rodungsbewilligung am 29. Mai 2001 bis zum 30. Juni 2006. Dieser Beschluss wurde zahlreichen Institutionen und Verbänden eröffnet, nicht jedoch den privaten Rekurrenten des ersten Rodungsbewilligungsverfahrens. Am 24. Juni 2004 erhoben A./B.X._ sowie C./D.Y._ Rekurs beim Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht), nachdem ihnen auf Anfrage der Entwurf der Rodungsbewilligungsverlängerung vom 29. Mai 2001 zugestellt worden war. In ihrer Rekursbegründung vom 27. August 2004 beantragten sie, es sei festzuhalten, dass die Rodungsbewilligungsverlängerung nichtig sei. Die Rodungsbewilligungsverlängerung sei aufzuheben oder eventualiter an die Vorinstanz zur erneuten Prüfung zurückzuweisen. Gleichzeitig stellten sie u.a. den "dringenden" Antrag um Zuerkennung der aufschiebenden Wirkung. Am 3. September 2004 wies die Präsidentin des Appellationsgerichts (als Verwaltungsgericht) das Gesuch um Erteilung der aufschiebenden Wirkung ab. Die dagegen eingereichte Verwaltungsgerichtsbeschwerde hiess das Bundesgericht mit Entscheid 1A.102/2004 vom 17. September 2004 gut, da Art. 47 WaG von Gesetzes wegen im Verfahren der Rodungsbewilligung die aufschiebende Wirkung vorsieht. Am 3. September 2004 wies die Präsidentin des Appellationsgerichts (als Verwaltungsgericht) das Gesuch um Erteilung der aufschiebenden Wirkung ab. Die dagegen eingereichte Verwaltungsgerichtsbeschwerde hiess das Bundesgericht mit Entscheid 1A.102/2004 vom 17. September 2004 gut, da Art. 47 WaG von Gesetzes wegen im Verfahren der Rodungsbewilligung die aufschiebende Wirkung vorsieht. D. Mit Urteil vom 7. März 2005 hat das Appellationsgericht (als Verwaltungsgericht) materiell entschieden und den Rekurs abgewiesen. Dagegen erheben A./B.X._ sowie C./D.Y._ mit Eingabe vom 3. Mai 2005 Verwaltungsgerichtsbeschwerde beim Bundesgericht und beantragen die Aufhebung des vorinstanzlichen Urteils. Das Wirtschafts- und Sozialdepartement des Kantons Basel-Stadt schliesst namens des Regierungsrates auf Abweisung der Beschwerde. Das Appellationsgericht (als Verwaltungsgericht) beantragt ebenfalls die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das BUWAL hat sich mit Schreiben vom 20. Juni 2005 vernehmen lassen. In ihrer Stellungnahme zu den Vernehmlassungen der Vorinstanz, des Wirtschafts- und Sozialdepartementes und des BUWALs halten die Beschwerdeführer an ihren Anträgen fest. 