Sachverhalt: Sachverhalt: A. Mit Verfügung vom 29. April 2002 genehmigte das Bundesamt für Verkehr (im Folgenden: Bundesamt) die Planvorlage der Appenzeller Bahnen vom 24. August 2001 betreffend Aufhebung des Bahnübergangs Riethüsli in der Stadt St. Gallen. Danach soll der direkte Zugang von der Riethüslistrasse zur Teufener Strasse (Kantonsstrasse) geschlossen und die Riethüslistrasse zur Sackgasse werden; der Bahnübergang soll nur noch für Fussgänger geöffnet bleiben. Die Riethüslistrasse wäre somit für den Fahrverkehr nur noch über die Demutstrasse erreichbar, welche ca. 200 m nördlich des Bahnübergangs Riethüsli in die Teufenerstrasse mündet. A. Mit Verfügung vom 29. April 2002 genehmigte das Bundesamt für Verkehr (im Folgenden: Bundesamt) die Planvorlage der Appenzeller Bahnen vom 24. August 2001 betreffend Aufhebung des Bahnübergangs Riethüsli in der Stadt St. Gallen. Danach soll der direkte Zugang von der Riethüslistrasse zur Teufener Strasse (Kantonsstrasse) geschlossen und die Riethüslistrasse zur Sackgasse werden; der Bahnübergang soll nur noch für Fussgänger geöffnet bleiben. Die Riethüslistrasse wäre somit für den Fahrverkehr nur noch über die Demutstrasse erreichbar, welche ca. 200 m nördlich des Bahnübergangs Riethüsli in die Teufenerstrasse mündet. B. Bereits im Sommer 2000 war auf Gesuch der Appenzeller Bahnen ein kantonales Strassenprojekt eingeleitet worden. Der Stadtrat von St. Gallen hatte im Rahmen dieses Verfahrens die Aufhebung der Einmündung der Riethüsli- in die Teufener Strasse erwogen, verzichtete jedoch angesichts der eingegangenen Einsprachen mit Beschluss vom 16. August 2001 auf die Weiterführung des Projekts. Dieser Entscheid wurde nicht angefochten. B. Bereits im Sommer 2000 war auf Gesuch der Appenzeller Bahnen ein kantonales Strassenprojekt eingeleitet worden. Der Stadtrat von St. Gallen hatte im Rahmen dieses Verfahrens die Aufhebung der Einmündung der Riethüsli- in die Teufener Strasse erwogen, verzichtete jedoch angesichts der eingegangenen Einsprachen mit Beschluss vom 16. August 2001 auf die Weiterführung des Projekts. Dieser Entscheid wurde nicht angefochten. C. Gegen die Verfügung des Bundesamts erhoben A._, B._ und C._ am 3. Juni 2002 Beschwerde bei der Rekurskommission des eidgenössischen Departements für Umwelt, Verkehr, Energie und Kommunikation (im Folgenden: Rekurskommission). Diese führte am 22. November 2002 einen Augenschein in Anwesenheit der Parteien durch. Am 23. April 2003 wies sie die Beschwerde ab und auferlegte den Beschwerdeführenden zwei Drittel der Verfahrenskosten. C. Gegen die Verfügung des Bundesamts erhoben A._, B._ und C._ am 3. Juni 2002 Beschwerde bei der Rekurskommission des eidgenössischen Departements für Umwelt, Verkehr, Energie und Kommunikation (im Folgenden: Rekurskommission). Diese führte am 22. November 2002 einen Augenschein in Anwesenheit der Parteien durch. Am 23. April 2003 wies sie die Beschwerde ab und auferlegte den Beschwerdeführenden zwei Drittel der Verfahrenskosten. D. Dagegen erhoben A._, B._ und C._ Verwaltungsgerichtsbeschwerde ans Bundesgericht. Sie beantragen, der angefochtene Rekursentscheid sei aufzuheben und es sei auf das Plangenehmigungsgesuch der Appenzeller Bahnen nicht einzutreten; eventualiter sei das Plangenehmigungsgesuch abzuweisen; subeventualiter sei das Plangenehmigungsgesuch an das Bundesamt oder subsubeventualiter an die Rekurskommission zu neuer Entscheidung zurückzuweisen. D. Dagegen erhoben A._, B._ und C._ Verwaltungsgerichtsbeschwerde ans Bundesgericht. Sie beantragen, der angefochtene Rekursentscheid sei aufzuheben und es sei auf das Plangenehmigungsgesuch der Appenzeller Bahnen nicht einzutreten; eventualiter sei das Plangenehmigungsgesuch abzuweisen; subeventualiter sei das Plangenehmigungsgesuch an das Bundesamt oder subsubeventualiter an die Rekurskommission zu neuer Entscheidung zurückzuweisen. E. Die Appenzeller Bahnen und die Rekurskommission beantragen, die Beschwerde sei abzuweisen. Das Bundesamt hat auf eine Vernehmlassung verzichtet. Im zweiten Schriftenwechsel hielten die Parteien an ihren Anträgen fest. 