Sachverhalt:
A.
A._ (geb. 1996) stammt aus Guinea. Am 2. September 2013 reiste er über Spanien illegal in die Schweiz ein und stellte im Empfangs- und Verfahrenszentrum U._ ein Asylgesuch. In der Folge wurde er für die Dauer des Asylverfahrens dem Kanton Zug zugewiesen. Am 26. Februar 2014 teilten die Sozialen Dienste Asyl des Kantons Zug dem Amt für Migration des Kantons Zug (hiernach: Amt für Migration) mit, dass A._ untergetaucht sei. Am 9. Juli 2014 führte die Kantonspolizei Genf A._ in den Kanton Zug zurück.
Mit zwei Strafbefehlen vom 9. Juli 2014 und 29. Juli 2014 verurteilten die Genfer Strafbehörden A._ wegen Verstosses gegen das Ausländergesetz und das Betäubungsmittelgesetz zu bedingten Geldstrafen von 20 und 40 Tagessätzen à Fr. 30.-- bei einer Probezeit von drei Jahren. Mit Strafbefehl vom 14. September 2015 wurde A._ von der Staatsanwaltschaft Zürich-Limmat wegen einfacher Körperverletzung mit einem gefährlichen Gegenstand zu einer weiteren bedingten Geldstrafe von 180 Tagessätzen à Fr. 30.-- bei einer Probezeit von zwei Jahren verurteilt.
Mit Verfügung vom 14. Oktober 2015 wies das Staatssekretariat für Migration (hiernach: SEM) das Asylgesuch von A._ ab und wies ihn aus der Schweiz weg. Die am 13. November 2015 dagegen erhobene Beschwerde wurde am 10. Dezember 2015 zufolge Rückzugs abgeschrieben. Das SEM setzte A._ eine neue Ausreisefrist bis zum 8. Januar 2016.
Am 3. Januar 2016 nahm ihn die Schweizer Grenzwache beim Versuch fest, am Grenzübergang Basel-Freiburgerstrasse von Deutschland in die Schweiz einzureisen. Am 21. Januar 2016 wurde er von der Staatsanwaltschaft Zürich-Limmat wegen illegaler Ein-, Aus- und Wiedereinreise bzw. illegalen Aufenthalts zu einer unbedingten Freiheitsstrafe von 120 Tagen verurteilt. Nach Rücküberstellung nach Zug am 22. Januar 2016 verfügte das Amt für Migration eine Eingrenzung auf das Gebiet der Gemeinde V._, wobei es ihm das rechtliche Gehör gewährte. Vorladungen vom 16. März, 21. März und 23. März 2016 leistete A._ keine Folge. Am 11. April 2016 vermeldeten die Sozialen Dienste Asyl des Kantons Zug erneut seinen unabgemeldeten Weggang. Am 21. April 2016 wurde A._ anlässlich einer Fahrzeugkontrolle durch die Aargauer Polizei festgenommen und zum Vollzug der unbedingten Freiheitsstrafe an die Züricher Strafvollzugsbehörden überstellt. Am 13. Juli 2016 wurde er aus dem Strafvollzug entlassen und den Zuger Behörden rücküberstellt.
B.
Am 13. Juli 2016 ordnete das Amt für Migration gestützt auf Art. 76 Abs. 1 lit. b Ziff. 1 i.V.m. Art. 75 Abs. 1 lit. b und Art. 76 Abs. 1 lit. b Ziff. 4 AuG (SR 142.20) die Ausschaffungshaft für die vorläufige Dauer von drei Monaten, d.h. bis zum 12. Oktober 2016 an, welcher der Haftrichter des Verwaltungsgerichts des Kantons Zug mit Verfügung vom 15. Juli 2016 die Genehmigung erteilte.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten und subsidiärer Verfassungsbeschwerde vom 16. August 2016 beantragt A._ sinngemäss die Aufhebung des vorinstanzlichen Entscheids sowie seine umgehende Haftentlassung. Sollte seinem Antrag auf umgehende Entlassung nicht stattgegeben werden, sei die Sache zu neuer Beurteilung an die Vorinstanz zurückzuschicken.
Mit Präsidialverfügung vom 19. August 2016 wurde das Begehren um sofortige Haftentlassung abgewiesen.
Das Verwaltungsgericht des Kantons Zug, das Amt für Migration sowie das Staatssekretariat für Migration beantragen die Abweisung der Beschwerde.
Am 8. September 2016 - und damit verspätet - hat A._ eine weitere Stellungnahme eingereicht.

Erwägungen:
1.
Gegen letztinstanzliche kantonale Gerichtsentscheide betreffend die Zwangsmassnahmen im Ausländerrecht steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen, soweit der Betroffene am vorinstanzlichen Verfahren teilgenommen hat, durch den angefochtenen Entscheid besonders berührt ist und an der Beurteilung seiner Eingabe ein aktuelles praktisches Interesse hat (Art. 86 Abs. 1 und 2, Art. 89 Abs. 1 BGG; Urteil 2C_112/2016 vom 19. Februar 2016 E. 1). Der Beschwerdeführer befindet sich gestützt auf den hier angefochtenen Entscheid bis zum 12. Oktober 2016 in Ausschaffungshaft. Er hat ein aktuelles Interesse, entlassen zu werden. Auf die frist- und formgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist einzutreten. Damit ist die subsidiäre Verfassungsbeschwerde ausgeschlossen (Art. 113 BGG), weshalb auf das Rechtsmittel insoweit nicht einzutreten ist.
2.
Der Beschwerdeführer rügt die Verletzung verschiedener verfassungsmässiger Rechte (Art. 9, 10 Abs. 2, 13, 14 und Art. 29 Abs. 2 BV). Er legt aber nicht ansatzweise dar, worin die genannten Bestimmungen durch die Vorinstanz verletzt worden seien. Damit genügt seine Eingabe den strengen Begründungsanforderungen hinsichtlich Verfassungsrügen (Art. 106 Abs. 2 BGG) nicht, weshalb nicht weiter darauf eingegangen werden kann.
3.
Die vorliegend zu beurteilende Haft wurde gestützt auf Art. 76 Abs. 1 lit. b Ziff. 1 i.V.m. Art. 75 Abs. 1 lit. b AuG und Art. 76 Abs. 1 lit. b Ziff. 4 AuG angeordnet.
3.1. Gemäss Art. 76 Abs. 1 lit. b AuG kann die zuständige Behörde nach Eröffnung eines erstinstanzlichen, nicht notwendigerweise rechtskräftigen Weg- oder Ausweisungsentscheids die davon betroffene Person zur Sicherstellung des Vollzugs der Massnahme in Haft nehmen, wenn ein gesetzlicher Haftgrund vorliegt und auch die übrigen gesetzlichen Voraussetzungen (namentlich Art. 79 - 81 AuG) gegeben sind. So kann die Ausschaffungshaft etwa angeordnet werden, wenn die betroffene Person gegen Ein- oder Ausgrenzungsverfügungen verstösst (Art. 76 Abs. 1 lit. b Ziff. 1 i.V.m. Art. 75 Abs. 1 lit. b AuG). Ein weiterer Haftgrund liegt darin, dass das bisherige Verhalten der Person darauf schliessen lässt, dass sie sich behördlichen Anordnungen widersetzen wird (Art. 76 Abs. 1 lit. b Ziff. 4 AuG).
3.2. Den vorinstanzlichen Sachverhaltsfeststellungen zufolge hat der Beschwerdeführer wiederholt behördliche Anordnungen missachtet. Er verliess zwei Mal über längere Zeit die ihm zugewiesene Unterkunft ohne entsprechende Abmeldung, um unterzutauchen. Des Weiteren leistete er mehreren behördlichen Vorladungen keine Folge. Schliesslich ist auch eine Verletzung der gegen ihn im Januar 2016 verfügten Eingrenzung auf das Gebiet der Gemeinde V._ erstellt, wurde er doch am 21. April 2016 im Kanton Aargau festgenommen. Von Bedeutung ist auch die Tatsache, dass er vier Mal strafrechtlich verurteilt wurde, namentlich wegen eines Betäubungsmitteldelikts und einfacher Körperverletzung mit einem gefährlichen Gegenstand. Rechtsprechungsgemäss ist bei einem straffälligen Ausländer eher als bei einem unbescholtenen davon auszugehen, er werde in Zukunft behördliche Anordnungen missachten (vgl. <ref-ruling> E. 3 S. 58 f.; <ref-ruling> E. 2a S. 51; 148 E. 2b/aa S. 152; <ref-ruling> E. 2b S. 198). Insgesamt ist daher nicht zu beanstanden, dass die Vorinstanz die angerufenen Haftgründe (Art. 76 Abs. 1 lit. b Ziff. 1 i.V.m. Art. 75 Abs. 1 lit. b und Art. 76 Abs. 1 lit. b Ziff. 4 AuG) im Urteilszeitpunkt als erfüllt erachtete. Dies wird vom Beschwerdeführer auch nicht bestritten.
4.
Der Beschwerdeführer rügt indessen eine Verletzung von Art. 80 Abs. 6 lit. a AuG. Er macht im Wesentlichen geltend, er habe ein Asylgesuch gestellt und das Asylverfahren sei nicht abgeschlossen. Bis zu einem rechtskräftigen Asylentscheid, der nicht in absehbarer Zeit erfolgen würde, könne seine Wegweisung nicht vollzogen werden.
4.1. Gemäss Art. 80 Abs. 6 lit. a AuG ist die Haft zu beenden, wenn der Haftgrund entfällt oder sich erweist, dass der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar ist. Diesfalls lässt sie sich nicht mehr mit einem hängigen Ausweisungsverfahren rechtfertigen und verstösst gegen Art. 5 Ziff. 1 lit. f EMRK (<ref-ruling> E. 4.1.1 S. 60 mit Hinweisen; <ref-ruling> E. 3 S. 152 f.). Wie es sich mit der Durchführbarkeit des Weg- oder Ausweisungsvollzugs im Einzelnen verhält, bildet Gegenstand einer nach pflichtgemässem Ermessen vorzunehmenden Prognose. Massgebend ist, ob die Ausschaffung mit hinreichender Wahrscheinlichkeit innert absehbarer Zeit möglich erscheint oder nicht. Die Haft hat, weil unverhältnismässig, dann als unzulässig zu gelten, wenn triftige Gründe dafür sprechen, dass die Wegweisung innert vernünftiger Frist nicht vollzogen werden kann (<ref-ruling> E. 4.1.3 S. 61 mit Hinweisen).
4.2. Die Vorinstanz ging davon aus, dass mit dem negativen Asylentscheid (und dem gleichzeitig verfügten Wegweisungsentscheid) des SEM vom 14. Oktober 2015 sowie dem Abschreibungsentscheid des Bundesverwaltungsgerichts vom 10. Dezember 2015 ein zulässiger Wegweisungstitel im Sinne von Art. 76 Abs. 1 AuG vorliege. Der Beschwerdeführer hat jedoch am 14. Juli 2016 - d.h. einen Tag nach Anordnung der Ausschaffungshaft durch das Amt für Migration und einen Tag vor der richterlichen Genehmigung derselben - ein weiteres Asylgesuch eingereicht. Es stellt sich die Frage, ob der Haftrichter unter diesen Umständen die Rechtmässigkeit der angeordneten Ausschaffungshaft bestätigen durfte.
4.2.1. Die Ausschaffungshaft soll den Vollzug der geplanten Entfernungsmassnahme sicherstellen und muss ernsthaft geeignet sein, diesen Zweck zu erreichen (<ref-ruling> E. 4.1.1. S. 59). Wird ein Asylgesuch gestellt, entfällt nach Art. 42 AsylG (SR 142.31) die Verpflichtung zur Ausreise. Der Ausländer ist berechtigt, bis zum Abschluss des Verfahrens in der Schweiz zu verbleiben. Grundsätzlich kommt in einem solchen Fall keine Ausschaffungshaft im Sinne von Art. 76 AuG in Frage, sondern es kann höchstens eine Vorbereitungshaft nach Art. 75 AuG angeordnet werden, welche nicht die Sicherstellung des Vollzugs eines Weg- oder Ausweisungsentscheids bezweckt, sondern der Durchführung eines Wegweisungsverfahrens dient (vgl. <ref-ruling> E. 2b S. 380).
4.2.2. Die Fortsetzung der Ausschaffungshaft ist jedoch nicht in jedem Fall ausgeschlossen, wenn die betroffene ausländische Person während der Ausschaffungshaft ein Asylgesuch stellt. Das Bundesgericht erachtet in einem solchen Fall die Fortsetzung der Ausschaffungshaft unter der Voraussetzung für zulässig, dass mit dem Abschluss des Asylverfahrens und dem Vollzug der Wegweisung in absehbarer Zeit gerechnet werden kann (vgl. <ref-ruling> E. 2.3.3 S. 413; <ref-ruling> E. 2b S. 380).
Diese Voraussetzungen waren vorliegend im Zeitpunkt des haftrichterlichen Entscheids erfüllt. Mit Blick auf die Tatsache, dass ein erstes Asylgesuch des Beschwerdeführers nur wenige Monate zuvor abgewiesen worden war, durfte der Haftrichter annehmen, dass das zweite Asylgesuch vom SEM möglicherweise als Wiedererwägungsgesuch behandelt werden würde. Dies hätte einerseits den ursprünglichen Wegweisungsentscheid nicht in Frage gestellt (vgl. Urteil 2A.714/2004 vom 3. Januar 2005 E. 2.1 mit Hinweis) und andererseits kann in einem solchen Fall mit einer raschen Behandlung des Gesuchs gerechnet werden (Wiedererwägungsgesuche werden in der Regel innerhalb von zehn Arbeitstagen behandelt, vgl. Art. 111b Abs. 2 zweiter Satz AsylG). Darüber hinaus hat der Haftrichter in seinem Entscheid das Amt für Migration angehalten, das SEM auf die zeitliche Dringlichkeit der Behandlung des Asylgesuchs hinzuweisen. Triftige Gründe für die Undurchführbarkeit des Ausschaffungsvollzugs lagen im Urteilszeitpunkt keine vor und wurden auch vom Beschwerdeführer in der mündlichen Verhandlung nicht geltend gemacht. Somit durfte der Haftrichter im Zeitpunkt des vorinstanzlichen Entscheids davon ausgehen, dass mit dem Abschluss des Asylverfahrens und dem Vollzug der Wegweisung in absehbarer Zeit zu rechnen ist.
Die Richtigkeit dieser Einschätzung hat sich im Übrigen in der Folge bestätigt. Das vom Beschwerdeführer am 14. Juli 2016 eingereichte Asylgesuch wurde bereits am 20. Juli 2016 vom SEM abgelehnt, welches sowohl die Wegweisung aus der Schweiz als auch den Wegweisungsvollzug angeordnet hat. Damit lag bereits wenige Tage nach Einreichung des Asylgesuchs erneut ein Wegweisungstitel im Sinne von Art. 76 AuG vor. Die vom Beschwerdeführer gegen die Verfügung des SEM eingereichte Beschwerde beim Bundesverwaltungsgericht ändert daran nichts, ist doch - entgegen seiner Auffassung - für die Ausschaffungshaft neben dem Vorliegen der (hier erfüllten) gesetzlichen Haftgründe nur erforderlich, dass ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet wurde, nicht aber dass dieser rechtskräftig ist. Im Übrigen hat das Bundesverwaltungsgericht mit Zwischenverfügung vom 23. August 2016 die Gesuche des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege und um Verzicht auf die Erhebung eines Kostenvorschusses - wegen Verdachts auf mutwillige Prozessführung - abgewiesen. Der Beschwerde wurde keine aufschiebene Wirkung erteilt. Auch macht der Beschwerdeführer nicht geltend, den geforderten Kostenvorschuss fristgemäss geleistet zu haben. Damit ist äusserst fraglich, ob das Bundesverwaltungsgericht überhaupt auf die Beschwerde eintreten wird. Auch diese Umstände sprechen dafür, dass mit einem baldigen Abschluss des (zweiten) Asylverfahrens zu rechnen ist.
4.2.3. Andere Gründe, die dafür sprechen würden, dass die Wegweisung nicht innert absehbarer Frist vollzogen werden könne bzw. dass die zuständigen Behörden den Vollzug nicht mit dem nötigen Nachdruck verfolgten, bringt der Beschwerdeführer vor Bundesgericht nicht vor. Solche sind auch nicht ersichtlich. In ihren Vernehmlassungen äussern sich sowohl das Amt für Migration als auch das SEM dahingehend, dass die guineische Vertretung in Genf die Ausstellung eines Laisser-passer für den Beschwerdeführer in Aussicht gestellt habe. Zudem hat das SEM die prioritäre Behandlung des Dossiers zugesichert, was ebenfalls für einen Wegweisungsvollzug in absehbarer Zeit spricht.
Sollte sich zeigen, dass die Behörden den vorliegenden Fall im Hinblick auf die Wegweisung des Beschwerdeführers bzw. den Vollzug derselben nicht beförderlich behandeln, wäre die Situation gegebenenfalls anders zu beurteilen. Je nach der weiteren Entwicklung des Falles werden die kantonalen Behörden diese Frage neu zu prüfen und allenfalls der geänderten Sachlage im Rahmen eines Haftentlassungsgesuchs oder von Amtes wegen Rechnung zu tragen haben.
Nach dem Gesagten liegen keine rechtlichen oder tatsächlichen Gründe im Sinne von Art. 80 Abs. 6 lit. a AuG vor, welche den Vollzug der Wegweisung als undurchführbar erscheinen liessen. Die Rüge des Beschwerdeführers erweist sich damit als unbegründet.
4.3. Der Beschwerdeführer macht schliesslich geltend, die Inhaftierung sei unverhältnismässig, da auch mit einer weniger einschneidenden Massnahme wie dem Rayonverbot der gewünschte Zweck erreicht würde. Dies trifft vorliegend nicht zu. Der Beschwerdeführer hat durch sein Verhalten zum Ausdruck gebracht, dass milderere Massnahmen nicht die gewünschte Wirkung zeigen, wurde doch die Ausschaffungshaft unter anderem deshalb angeordnet, weil er eine gegen ihn im Januar 2016 verfügte Eingrenzung auf das Gebiet der Gemeinde V._ missachtet hat.
Ebenso unbehelflich ist sein Vorbringen, ein Ehevorbereitungsverfahren vor dem Zivilstandsamt von W._ sei anhängig. Zum einen konnte gemäss den Sachverhaltsfeststellungen der Vorinstanz das Ehevorbereitungsverfahren mangels rechtsgenüglicher Identitätspapiere nicht weitergeführt werden. Zum anderen ist es dem Beschwerdeführer, der seiner Ausreisepflicht nicht nachgekommen ist, zuzumuten, seine Partnerin im Ausland zu heiraten oder den Ausgang eines allfälligen Bewilligungsverfahrens in seiner Heimat abzuwarten.
5.
Insgesamt sind keine Gründe ersichtlich, welche die Rechtmässigkeit der Haft in Frage zu stellen vermöchten. Der angefochtene Entscheid verletzt somit kein Bundesrecht.
Nach dem Ausgeführten ist die Beschwerde abzuweisen.
Die Umstände des Falls rechtfertigen es, ausnahmsweise auf die Erhebung von Gerichtskosten zu verzichten (Art. 66 Abs. 1 zweiter Satz BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2.
Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3.
Es werden keine Kosten erhoben.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zug, Haftrichter, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 13. September 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Petry