Sachverhalt:
A.
Mit Baugesuch vom 20. August 2012 beantragte X._ die Erteilung einer Baubewilligung für den Neubau eines Einfamilienhauses auf Parzelle 1623 in Cavorgia, Gemeinde Tujetsch. Dagegen erhob die Vereinigung Helvetia Nostra Einsprache. Das Bauamt Tujetsch trat auf die Einsprache am 17. Dezember (mitgeteilt am 21. Dezember) 2012 mangels Legitimation nicht ein und erteilte am 21. Dezember 2012 die Baubewilligung.
B.
Die dagegen erhobene Beschwerde der Helvetia Nostra wies das Verwaltungsgericht des Kantons Graubünden am 19. Februar 2013 ab. Es entschied, die Gemeinde sei zu Recht auf die Einsprache der Helvetia Nostra nicht eingetreten.
Im Übrigen ging es davon aus, dass <ref-law> erst auf Baubewilligungen anwendbar sei, die nach dem 1. Januar 2013 erteilt würden. Daraus ergebe sich, dass auch in Gemeinden wie Tujetsch, in denen die kritische Grenze von 20 % Zweitwohnungen überschritten sei, im Jahr 2012 noch Baubewilligungen für Zweitwohnungen nach bisherigem Recht erteilt werden durften.
C.
Dagegen erhob die Helvetia Nostra am 18. März 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragt, der angefochtene Entscheid sei aufzuheben und die Sache zu neuem Entscheid an das Verwaltungsgericht zurückzuweisen. Eventualiter sei die dem Projekt von X._ in Tujetsch erteilte Baubewilligung aufzuheben.
D.
Das Verfahren wurde bis zum Vorliegen eines Grundsatzentscheids des Bundesgerichts zur Frage der Beschwerdebefugnis der Helvetia Nostra und der Anwendbarkeit von <ref-law> und <ref-law> zurückgestellt.
Am 22. Mai 2013 fällte das Bundesgericht die ersten Leitentscheide: Es bejahte die Beschwerdebefugnis der Helvetia Nostra (<ref-ruling>) sowie die direkte Anwendbarkeit von <ref-law> und <ref-law> ab dem 11. März 2012 (<ref-ruling> und 263).
E.
Im Anschluss an diese Urteile wurde das Verfahren fortgesetzt und dem Beschwerdegegner, der Gemeinde Tujetsch und dem Verwaltungsgericht Gelegenheit zur Stellungnahme eingeräumt.
Der Rechtsvertreter von X._ teilt mit, dass sich sein Mandant in Bangalore (Indien) aufhalte und sich daher bei seinem früheren Einwohneramt im Kanton Basel Stadt abgemeldet habe. Er beabsichtige, bei seiner Rückkehr allenfalls Wohnsitz in der Gemeinde Tujetsch zu nehmen. Dafür habe er auch das Baugesuch im Sinne einer Erstwohnung eingereicht.
Die Gemeinde Tujetsch und das Verwaltungsgericht haben sich nicht vernehmen lassen.

Erwägungen:
1.
Die Plafonierung des Zweitwohnungsbaus gemäss <ref-law> stellt eine Bundesaufgabe dar, die der Schonung der Natur und des heimatlichen Landschaftsbildes dient. Die nach Art. 12 Abs. 1 lit. b des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451) beschwerdebefugten Organisationen im Bereich des Natur- und Heimatschutzes - zu denen auch die Helvetia Nostra gehört - können daher Baubewilligungen wegen Verletzung von <ref-law> und seiner Übergangs- und Ausführungsbestimmungen anfechten (<ref-ruling> E. 11 S. 276 ff.). Das Verwaltungsgericht und die Gemeinde Tujetsch haben somit die Einsprachebefugnis der Beschwerdeführerin zu Unrecht verneint.
2.
Das Verwaltungsgericht ging überdies davon aus, dass die neuen Verfassungsbestimmungen nicht anwendbar seien auf Baubewilligungen, die zwischen dem 11. März 2012 und dem 31. Dezember 2012 erstinstanzlich erteilt wurden (<ref-law> e contrario).
Das Bundesgericht hat in <ref-ruling> (E. 9-11 S. 249 ff.) entschieden, dass <ref-law> seit seinem Inkrafttreten am 11. März 2012 anwendbar ist. Zwar bedarf diese Bestimmung in weiten Teilen der Ausführung durch ein Bundesgesetz. Unmittelbar anwendbar ist sie jedoch insoweit, als sie (in Verbindung mit <ref-law>) ein Baubewilligungsverbot für Zweitwohnungen in allen Gemeinden anordnet, in denen der 20 %-Zweitwohnungsanteil bereits erreicht oder überschritten ist. Dies hat zur Folge, dass Baubewilligungen für Zweitwohnungen, die zwischen dem 11. März 2012 und dem 31. Dezember 2012 in den betroffenen Gemeinden erteilt wurden, auf Beschwerde aufzuheben sind.
3.
Nach dem Gesagten steht fest, dass der angefochtene Entscheid aufzuheben ist. Fraglich ist, ob die Sache an das Verwaltungsgericht oder - unter Mitaufhebung des Einspracheentscheids und der Baubewilligung - an die erste Instanz, d.h. an die Gemeinde Tujetsch, zurückzuweisen ist (<ref-law>).
Für letztere Lösung spricht der Umstand, dass die Gemeinde Tujetsch zu Unrecht auf die Einsprache der Helvetia Nostra nicht eingetreten ist, sich also noch nicht mit deren Einwänden befasst hat.
Hinzu kommt, dass das Bauvorhaben in der ursprünglichen Form, ohne Nutzungsbeschränkung, gegen <ref-law> verstösst. Die vom Beschwerdegegner nunmehr beabsichtigte Bewilligung als Erstwohnung setzt Modifikationen des Baugesuchs voraus, zu denen der Helvetia Nostra im Einspracheverfahren das rechtliche Gehör gewährt werden muss.
Unter diesen Umständen erscheint es sinnvoll, in Gutheissung des Eventualantrags der Beschwerdeführerin den Einspracheentscheid und die Baubewilligung aufzuheben und die Sache an die Gemeinde Tujetsch zurückzuweisen.
Will der Beschwerdegegner an seinem Bauvorhaben festhalten, muss er das Baugesuch mit den nötigen Angaben ergänzen. Verzichtet er dagegen auf das Baugesuch, kann die Gemeinde einen Abschreibungsbeschluss erlassen und darin auch ihre Kosten neu verlegen.
4.
Bei diesem Ausgang des Verfahrens obsiegt die Beschwerdeführerin. Der private Beschwerdegegner wird daher kostenpflichtig, und zwar sowohl für das bundesgerichtliche Verfahren (<ref-law>) als auch für das Verfahren vor Verwaltungsgericht (<ref-law>).
Zwar hat er weder vor Verwaltungsgericht noch vor Bundesgericht die Abweisung der Beschwerde beantragt. Er hat jedoch durch die Einreichung des Baugesuchs das Verfahren veranlasst und ist deshalb im vorliegenden Verfahren notwendigerweise Gegenpartei bzw. Beschwerdegegner; als solcher trägt er grundsätzlich das Prozess- und Kostenrisiko (<ref-ruling> E. 3c S. 158).
Die Beschwerdeführerin war weder vor Verwaltungsgericht noch vor Bundesgericht anwaltlich vertreten, weshalb sie praxisgemäss keinen Anspruch auf eine Parteientschädigung hat.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Graubünden vom 19. Februar 2013, der Einspracheentscheid des Bauamts Tujetsch vom 17./21. Dezember 2012 sowie die Baubewilligung vom 21. Dezember 2012 werden aufgehoben. Die Sache wird im Sinne der Erwägungen an die Gemeinde Tujetsch zurückgewiesen.
2.
Die Gerichtskosten von Fr. 1'000.-- für das bundesgerichtliche Verfahren und Fr. 1'033.-- für das verwaltungsgerichtliche Verfahren werden dem Beschwerdegegner (X._) auferlegt.
3.
Es werden keine Parteientschädigungen zugesprochen.
4.
Dieses Urteil wird den Parteien, der Gemeinde Tujetsch und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 3. Oktober 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber