Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. Das Amt für Polizeiwesen, Asyl und Massnahmenvollzug, des Kantons Graubünden ordnete am 6. Mai 2004 gegen den armenischen Staatsangehörigen X._ die Ausschaffungshaft an und ersuchte am 7. Mai 2004 das Bezirksgericht Plessur um Genehmigung der Haft bis zum 5. August 2004. Nach mündlicher Verhandlung lehnte das Bezirksgerichtspräsidium Plessur das Gesuch ab und verfügte die unverzügliche Entlassung von X._ aus der Haft. Mit Verwaltungsgerichtsbeschwerde vom 7. Juni 2004 beantragte das Bundesamt für Flüchtlinge dem Bundesgericht, diesen Entscheid des Bezirksgerichtspräsidiums aufzuheben.
Die Verwaltungsgerichtsbeschwerde ist dem Rechtsanwalt zur Kenntnis gebracht worden, welcher dem Beschwerdegegner X._ im kantonalen Haftprüfungsverfahren als unentgeltlicher Rechtsanwalt beistand. Er ersucht im Hinblick auf die ihm zugestellte Einladung zur Vernehmlassung, er sei auch für das bundesgerichtliche Verfahren als unentgeltlicher Rechtsanwalt des Beschwerdegegners zu bestellen.
Die Verwaltungsgerichtsbeschwerde ist dem Rechtsanwalt zur Kenntnis gebracht worden, welcher dem Beschwerdegegner X._ im kantonalen Haftprüfungsverfahren als unentgeltlicher Rechtsanwalt beistand. Er ersucht im Hinblick auf die ihm zugestellte Einladung zur Vernehmlassung, er sei auch für das bundesgerichtliche Verfahren als unentgeltlicher Rechtsanwalt des Beschwerdegegners zu bestellen.
2. Gemäss Art. 152 Abs. 2 (in Verbindung mit Abs. 1) OG kann einer bedürftigen Partei, deren Rechtsbegehren nicht aussichtslos erscheint, nötigenfalls ein Rechtsanwalt beigegeben werden. Die Beigabe eines Rechtsanwalts ist an die Voraussetzung der Notwendigkeit ("nötigenfalls") geknüpft. Notwendig erscheint die Beigabe eines unentgeltlichen Rechtsbeistands im Sinne von Art. 152 Abs. 2 OG nur dann, wenn die Interessen einer Partei durch das in Frage stehende Verfahren in schwerwiegender Weise und unmittelbar betroffen sind (<ref-ruling> E. 4a S. 317 f. mit Hinweis). Der Fall muss in tatsächlicher und rechtlicher Hinsicht gewisse Schwierigkeiten bieten (vgl. zur Frage der unentgeltlichen Verbeiständung bei ausländerrechtlicher Haft in verfassungsrechtlicher Hinsicht <ref-ruling> und 275).
Sollte die vorliegende Verwaltungsgerichtsbeschwerde gutgeheissen werden, würde mit dem Urteil des Bundesgerichts nicht eine erneute Inhaftierung des Beschwerdegegners angeordnet. Hiefür wäre eine neue Haftverfügung erforderlich, und es wäre innert 96 Stunden die richterliche Überprüfung zu erwirken, welcher die dannzumal aktuellen Verhältnisse zu Grunde zu legen wären, wobei dann die Frage zu prüfen wäre, ob der Beschwerdegegner die Hilfe eines unentgeltlichen Rechtsanwalts beanspruchen könne (vgl. zu den entsprechenden Voraussetzungen und zu Unterschieden zwischen Haftanordnungs- und Haftverlängerungsverfahren <ref-ruling> und 275). Insofern hat der Ausgang des vorliegenden Beschwerdeverfahrens für den Beschwerdegegner keine unmittelbar wirksame schwerwiegende Auswirkung. Hinzu kommt, dass einzig zu prüfen ist, ob - entgegen der Darstellung im angefochtenen Entscheid - formlos eine Wegweisung angeordnet worden sei, bevor der Beschwerdegegner zum Ausdruck gebracht habe, dass er (wiederum) ein Asylgesuch stellen wolle. Diesbezüglich sind keine umfangreichen Abklärungen erforderlich; vielmehr wird diese Sachverhaltsfrage wohl ausschliesslich aufgrund der vorhandenen Akten zu beurteilen sein.
Unter diesen Umständen erscheint die Beigabe eines unentgeltlichen Rechtsanwalts nicht erforderlich. Das entsprechende Gesuch ist abzuweisen, ohne dass geprüft werden muss, welche Erfolgsaussichten ein allfälliges Begehren des Beschwerdegegners, die Verwaltungsgerichtsbeschwerde sei abzuweisen, hätte.
Abschliessend ist in Erinnerung zu rufen, dass dem Beschwerdegegner mit Verfügung vom 18. Juni 2004 rechtsgültig Frist zur Einreichung einer Vernehmlassung bis zum 16. August 2004 angesetzt worden ist.

Demnach beschliesst das Bundesgericht
im Verfahren nach Art. 152 OG:
im Verfahren nach Art. 152 OG:
1. Das Gesuch um unentgeltliche Verbeiständung des Beschwerdegegners wird abgewiesen.
1. Das Gesuch um unentgeltliche Verbeiständung des Beschwerdegegners wird abgewiesen.
2. Dieser Beschluss wird den Parteien, dem Amt für Polizeiwesen Graubünden, Asyl und Massnahmenvollzug, und dem Bezirksgerichtspräsidium Plessur schriftlich mitgeteilt.
Lausanne, 12. Juli 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber: