Sachverhalt: Sachverhalt: A. 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 zwischen den deutschen Städten Lörrach und Weil am Rhein. 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. 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 zwei betroffene Grundeigentümer beim Appellationsgericht (als Verwaltungsgericht) des Kantons Basel-Stadt Beschwerde, welche mit Urteil vom 7. März 2005 abgewiesen wurde. Das Bundesgericht schützte diesen Entscheid mit Urteil 1A.114/2005 vom 12. September 2005. 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 zwei betroffene Grundeigentümer beim Appellationsgericht (als Verwaltungsgericht) des Kantons Basel-Stadt Beschwerde, welche mit Urteil vom 7. März 2005 abgewiesen wurde. Das Bundesgericht schützte diesen Entscheid mit Urteil 1A.114/2005 vom 12. September 2005. B. Am 2. Dezember 2004 hatten zudem neun weitere Eigentümer von Grundstücken im betreffenden Gebiet das Wirtschafts- und Sozialdepartement (WSD) darum ersucht, ihnen die fragliche Verlängerung der Rodungsbewilligung vom 29. Mai 2001 zu eröffnen oder allenfalls einen Nichteintretensentscheid zu erlassen. Mit Regierungsratsbeschluss vom 25. Januar 2005 wurde der Standpunkt vertreten, den Gesuchstellern komme keine Parteistellung zu, weshalb ihnen die Verfügung vom 29. Mai 2001 nicht eröffnet werden müsse. B. Am 2. Dezember 2004 hatten zudem neun weitere Eigentümer von Grundstücken im betreffenden Gebiet das Wirtschafts- und Sozialdepartement (WSD) darum ersucht, ihnen die fragliche Verlängerung der Rodungsbewilligung vom 29. Mai 2001 zu eröffnen oder allenfalls einen Nichteintretensentscheid zu erlassen. Mit Regierungsratsbeschluss vom 25. Januar 2005 wurde der Standpunkt vertreten, den Gesuchstellern komme keine Parteistellung zu, weshalb ihnen die Verfügung vom 29. Mai 2001 nicht eröffnet werden müsse. C. Gegen diesen Entscheid gelangten die neun Grundeigentümer ans Verwaltungsgericht, welches den Rekurs mit Urteil vom 26. August 2005 abwies, soweit es darauf eintrat. Mit Eingabe vom 24. Oktober 2005 erheben X._ (Beschwerdeführer 1), Y._ (Beschwerdeführer 2) und Z._ (Beschwerdeführer 3) Verwaltungsgerichtsbeschwerde beim Bundesgericht und beantragen die Aufhebung des vorinstanzlichen Urteils. Das Appellationsgericht als Verwaltungsgericht wie auch das Sozial- und Wirtschaftsdepartement des Kantons Basel-Stadt (namens des Regierungsrates) schliessen auf Abweisung der Beschwerde. In ihrer Replik halten die Beschwerdeführer sinngemäss an ihren Anträgen fest. 