Sachverhalt:
Sachverhalt:
A. Im Anschluss an den Vollzug einer 20-tägigen Gefängnisstrafe nahm das Amt für Polizeiwesen Graubünden den vermutlich aus Armenien stammenden Y._ (geb. 1977) am 6. Mai 2004 in Ausschaffungshaft. Nach mündlicher Verhandlung wies das Bezirksgerichtspräsidium Plessur als Haftgericht den Antrag auf Bestätigung der Ausschaffungshaft am 10. Mai 2004 ab und ordnete die sofortige Haftentlassung von Y._ an.
A. Im Anschluss an den Vollzug einer 20-tägigen Gefängnisstrafe nahm das Amt für Polizeiwesen Graubünden den vermutlich aus Armenien stammenden Y._ (geb. 1977) am 6. Mai 2004 in Ausschaffungshaft. Nach mündlicher Verhandlung wies das Bezirksgerichtspräsidium Plessur als Haftgericht den Antrag auf Bestätigung der Ausschaffungshaft am 10. Mai 2004 ab und ordnete die sofortige Haftentlassung von Y._ an.
B. Mit Postaufgabe vom 10. Juni 2004 hat das Bundesamt für Flüchtlinge beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht. Es beantragt, den Entscheid des Bezirksgerichtspräsidiums Plessur vom 10. Mai 2004 aufzuheben.
B. Mit Postaufgabe vom 10. Juni 2004 hat das Bundesamt für Flüchtlinge beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht. Es beantragt, den Entscheid des Bezirksgerichtspräsidiums Plessur vom 10. Mai 2004 aufzuheben.
C. Y._ hat als Beschwerdegegner um unentgeltliche Verbeiständung ersucht. Mit Beschluss vom 12. Juli 2004 hat das Bundesgericht dieses Gesuch abgewiesen.
C. Y._ hat als Beschwerdegegner um unentgeltliche Verbeiständung ersucht. Mit Beschluss vom 12. Juli 2004 hat das Bundesgericht dieses Gesuch abgewiesen.
D. Y._ hat weder einen Antrag in der Hauptsache gestellt noch sich sonst vernehmen lassen. Das Bezirksgericht Plessur hat ausdrücklich auf eine Vernehmlassung verzichtet. Das Amt für Polizeiwesen Graubünden schliesst auf Gutheissung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. 1.1 Nach Art. 103 lit. b OG ist das in der Sache zuständige Departement oder, soweit das Bundesrecht es vorsieht, die in der Sache zuständige Dienstabteilung der Bundesverwaltung zur Verwaltungsgerichtsbeschwerde an das Bundesgericht berechtigt. Gemäss Art. 24 Abs. 2 der Organisationsverordnung vom 17. November 1999 für das Eidgenössische Justiz- und Polizeidepartement (OV-EJPD; SR 172.213.1; in der seit 1. Februar 2004 gültigen Fassung, AS 2004 436) ist das Bundesamt für Flüchtlinge (im Folgenden: Bundesamt) im Bereich der Zwangsmassnahmen im Ausländerrecht ermächtigt, Verwaltungsgerichtsbeschwerde gegen letztinstanzliche kantonale Entscheide zu führen.
1.2 Die Legitimation nach den genannten Bestimmungen hat zum Zweck, eine richtige und einheitliche Anwendung des Bundesrechts zu sichern. Die legitimierte Behörde hat daher nicht darzulegen, dass sie ein persönliches schutzwürdiges Interesse im Sinne von Art. 103 lit. a OG an der Aufhebung des angefochtenen Entscheides besitzt (<ref-ruling> E. 2c S. 329; <ref-ruling> E. 2c S. 21). Der Legitimation sind dennoch gewisse Grenzen gesetzt, indem ein hinreichendes praktisches Interesse an der Beurteilung der Beschwerde verlangt wird (vgl. <ref-ruling> E. 1 S. 196; Urteile 2A.96/2002 vom 16. April 2002, E. 1.2; 2A.148/2003 vom 30. Mai 2003, E. 1.1, und 2A.480/2003 vom 26. August 2004, E. 1). Ob hier ein derartiges Interesse vorliegt, ist im Folgenden zu prüfen.
1.2.1 Das Haftgericht hat die Bestätigung der Ausschaffungshaft mit der Begründung verweigert, es sei nicht erwiesen und ergebe sich insbesondere nicht aus den Akten, dass das Amt für Polizeiwesen den Beschwerdegegner vor Stellung eines (zweiten) Asylgesuchs formlos weggewiesen habe. Unter anderem werde in der Befragung des Beschwerdegegners vom 5. Mai 2004 weder auf eine formlose Wegweisung Bezug genommen noch der Inhaftierte darauf hingewiesen. Die Folge dieser Beweislosigkeit führe dazu, dass keine Ausschaffungshaft angeordnet werden könne.
Das Bundesamt macht demgegenüber geltend, die Eröffnung der formlosen Wegweisung gehe ohne Weiteres aus dem Protokoll der erwähnten Befragung vom 5. Mai 2004 hervor. In <ref-ruling> (E. 1.5 S. 106 f.) habe das Bundesgericht festgestellt, dass die Formerfordernisse für die Anordnung einer formlosen Wegweisung gering seien. Gegenstand der materiellen Prüfung sei daher, ob das Haftgericht mit seinem Entscheid die gefestigte Praxis des Bundesgerichts verletze. Es bestehe "für ähnlich gelagerte Einzelfälle ein grosses Interesse an der abstrakten Klärung dieser Frage".
1.2.2 Nach den Ausführungen des Bundesamts scheint es darum zu gehen, dass das Haftgericht die Anforderungen an die formlose Wegweisung verkannt habe. Das ist jedoch nicht der Fall. Das Haftgericht hat nicht festgehalten, es erkenne Erklärungen der Behörden nicht als formlose Wegweisung an oder verlange hierfür besondere Formerfordernisse. Es hat auch nicht die Beweislastregeln falsch angewendet (vgl. Urteile 2A.305/2001 vom 18. Juli 2001, E. 3d, und 2A.462/2003 vom 3. Oktober 2003, E. 2.3.2). Vielmehr hat es im Rahmen seiner Sachverhaltsfeststellung keinen Hinweis gefunden, dass vor dem Asylgesuch des Beschwerdegegners jemals von einer formlosen Wegweisung die Rede gewesen sein soll. Letztlich rügt das Bundesamt, dass diese Sachverhaltsfeststellung falsch sei. Mithin geht es nur darum, ob das Haftgericht den Sachverhalt richtig und vollständig festgestellt hat.
Fehler in der Feststellung des Sachverhalts bilden zwar einen - vorliegend durch Art. 105 Abs. 2 OG beschränkten - eigenständigen Beschwerdegrund (Art. 104 lit. b OG). Daher ist es an sich zulässig, mit Verwaltungsgerichtsbeschwerde allein die unrichtige oder unvollständige Feststellung des massgebenden Sachverhalts zu rügen. Es fragt sich jedoch, ob hierfür ein hinreichendes Interesse des Bundesamts gegeben ist.
1.2.3 Einerseits ist der Beschwerdegegner nach Eröffnung des angefochtenen Entscheids aus der Haft entlassen worden. Wie bereits im erwähnten Beschluss über die Verbeiständung vom 12. Juli 2004 ausgeführt wurde (vgl. oben lit. C), würde bei Gutheissung der vorliegenden Beschwerde mit dem Urteil des Bundesgerichts nicht eine erneute Inhaftierung des Beschwerdegegners angeordnet; es wäre vielmehr eine neue Haftverfügung erforderlich, die innert 96 Stunden wiederum richterlich zu überprüfen wäre, wobei die dannzumal aktuellen Verhältnisse zu Grunde zu legen wären (vgl. auch <ref-ruling> E. 5 S. 10). Ausserdem bliebe die Überprüfung des interessierenden Entscheids des Haftgerichts in einem allfälligen Staatshaftungsverfahren möglich, selbst wenn der Haftrichterentscheid nicht ans Bundesgericht weitergezogen wird und dadurch in Rechtskraft erwächst (<ref-ruling> E. 3 S. 142 ff.).
1.2.4 Andererseits soll - wie schon erklärt - das Beschwerderecht der Bundesbehörden den richtigen und rechtsgleichen Vollzug des Bundesverwaltungsrechts sicherstellen. Dabei muss grundsätzlich kein spezifisches öffentliches Interesse an der Aufhebung oder Änderung der angefochtenen Verfügung nachgewiesen werden. Es genügt, dass es der beschwerdeführenden Verwaltungseinheit nicht um die Behandlung abstrakter Fragen des objektiven Rechts, sondern um konkrete Rechtsfragen eines tatsächlich bestehenden Einzelfalles geht (<ref-ruling> E. 1.1 S. 3 f.; <ref-ruling> E. 1 S. 195).
1.2.5 Bei vergleichbarer Ausgangslage wie hier (Haftentlassung aufgrund des Haftrichterentscheids) hat das Bundesgericht verschiedentlich unter ausdrücklicher Berufung darauf, dass die Behandlung der aufgeworfenen Rechtsfrage Auswirkungen auf weitere Fälle haben könne, ein hinreichendes Interesse der Bundesbehörden bejaht (<ref-ruling> E. 1 S. 196; Urteile 2A.281/2000 vom 3. Oktober 2000, E. 1b; 2A.96/2002 vom 16. April 2002, E. 1.2; 2A.419/2002 vom 7. Oktober 2002, E. 1; 2A.197/2003 vom 16. Mai 2003, E. 2.1; 2A.148/2003 vom 30. Mai 2003, E. 1.1, und 2A.480/2003 vom 26. August 2004, E. 1). Andernorts hat es sich nicht explizit dazu geäussert, ob die Rechtsfrage Bedeutung für andere Fälle hat bzw. haben kann (vgl. <ref-ruling> E. 1.1 S. 4; Urteile 2A.241/2002 und 2A.242/2002, je vom 28. Juni 2002, je E. 1).
In einem Urteil vom 7. Juli 2003 hat das Bundesgericht erklärt, dass der Behörde die Beschwerdebefugnis nicht schon deswegen abzusprechen ist, weil sich keine Fragen grundsätzlicher Art stellen, die in der (publizierten und gefestigten) Bundesgerichtspraxis noch nicht beantwortet worden sind (Urteil 2A.268/2003, E. 2). Hieran ist festzuhalten. Die Zulassung der Behördenbeschwerde auf dem Gebiet der Zwangsmassnahmen im Ausländerrecht dient nicht nur dem Ziel, noch offene Rechtsfragen zu klären, sondern auch, eine einheitliche Praxis bei der Anwendung des Bundesrechts zu gewährleisten. Es soll vermieden werden, dass sich in den Kantonen eine unterschiedliche Rechtspraxis entwickelt, die mangels Zulässigkeit der Behördenbeschwerde vom Bundesgericht nicht mehr überprüft werden könnte. Im zuletzt erwähnten Urteil 2A.268/2003 war denn auch (bloss) zu überprüfen, ob der Haftrichter aufgrund des festgestellten Sachverhaltes das Vorliegen eines Haftgrundes in Anwendung der vom Bundesgericht entwickelten Kriterien verneinen durfte.
1.2.6 Die vorliegende Situation ist damit jedoch nicht vergleichbar. Hier geht es nach den Ausführungen in Erwägung 1.2.2 nicht um die Rüge der Verletzung von Bundesrecht gemäss Art. 104 lit. a OG, sondern um die Rüge der unrichtigen Feststellung des Sachverhalts gemäss Art. 104 lit. b OG (Übersehen einer Passage im Einvernahmeprotokoll). Es ist somit weder eine neue Rechtsfrage zu behandeln noch einer nicht bundesrechtskonformen Rechtsentwicklung Einhalt zu gebieten. Mit Blick auf die vorstehenden Ausführungen, unter anderem in Erwägung 1.2.3, hat das Bundesamt demzufolge kein hinreichendes Interesse, vom Bundesgericht überprüfen zu lassen, ob das Haftgericht den Sachverhalt richtig festgestellt hat.
1.2.6 Die vorliegende Situation ist damit jedoch nicht vergleichbar. Hier geht es nach den Ausführungen in Erwägung 1.2.2 nicht um die Rüge der Verletzung von Bundesrecht gemäss Art. 104 lit. a OG, sondern um die Rüge der unrichtigen Feststellung des Sachverhalts gemäss Art. 104 lit. b OG (Übersehen einer Passage im Einvernahmeprotokoll). Es ist somit weder eine neue Rechtsfrage zu behandeln noch einer nicht bundesrechtskonformen Rechtsentwicklung Einhalt zu gebieten. Mit Blick auf die vorstehenden Ausführungen, unter anderem in Erwägung 1.2.3, hat das Bundesamt demzufolge kein hinreichendes Interesse, vom Bundesgericht überprüfen zu lassen, ob das Haftgericht den Sachverhalt richtig festgestellt hat.
2. Nach dem Gesagten ist auf die Beschwerde des Bundesamts nicht einzutreten. Es sind keine Gerichtskosten zu erheben (Art. 156 Abs. 2 OG). Der Beschwerdegegner ist zwar anwaltlich vertreten; er hat sich im bundesgerichtlichen Verfahren jedoch nicht zur Sache geäussert, so dass ihm keine Parteientschädigung zuzusprechen ist.

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Auf die Verwaltungsgerichtsbeschwerde wird nicht eingetreten.
1. Auf die Verwaltungsgerichtsbeschwerde wird nicht eingetreten.
2. Es werden keine Kosten erhoben.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Parteien, dem Bezirksgerichtspräsidium Plessur und dem Amt für Polizeiwesen Graubünden, Asyl und Massnahmenvollzug, schriftlich mitgeteilt.
Lausanne, 1. Dezember 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: