Sachverhalt:
A.
In der Gemeinde Vals wird seit 1930 im Gebiet Carlag Stein abgebaut und gespalten. Am 17. Juni 2007 stimmten die Stimmberechtigten der Gemeinde Vals der Vorlage der projektbezogenen Nutzungsplanrevision "Abbauzone Carlag" zu. Die Regierung des Kantons Graubünden genehmigte diese Nutzungsplanung samt Generellem Gestaltungsplan am 19. August 2008. Die dagegen erhobene Beschwerde hiess das Verwaltungsgericht des Kantons Graubünden mit Urteil vom 28. April 2009 wegen Verletzung des rechtlichen Gehörs gut.
B.
Am 6. März 2008 verlangte X._ die unverzügliche Einstellung des Abbaus, für den noch keine Baubewilligung vorliege. Mit Verfügung vom 25. September 2008 forderte die Gemeinde die W._ AG auf, innert 30 Tagen ein Baugesuch für den Abbau von Steinen im Gebiet "Carlag" einzureichen. Auf Beschwerde der W._ AG änderte das Verwaltungsgericht im Urteil vom 28. April 2009 den angefochtenen Entscheid dahin ab, dass das Gesuch für das Bauen ausserhalb der Bauzone erst nach Rechtskraft des Nutzungsplanungsverfahrens gestellt werden müsse. Am 26. Juli 2010 (Urteil 1C_276/2009) hiess das Bundesgericht die dagegen erhobene Beschwerde von X._ gut und ordnete an, die W._ AG habe die Abbruchtätigkeit im Steinbruch "Carlag" bis zum 31. Oktober 2010 einzustellen.
C.
Am 20. Oktober 2010 reichte die W._ AG bei der Gemeinde Vals ein Gesuch um Weiterbetrieb des Steinbruchs "Carlag" ein. Der Gemeindevorstand wies das Gesuch am 12. April 2011 ab. Das Verwaltungsgericht wie auch das Bundesgericht (Urteil 1C_7/2012 vom 11. Juni 2012) wiesen die dagegen erhobene Beschwerde ab, weil das Vorhaben planungspflichtig sei und daher nicht auf dem Weg der Ausnahmebewilligung gemäss Art. 24 ff. RPG bewilligt werden könne.
D.
Am 22. Dezember 2011 reichte die W._ AG das Gesuch ein, auf Parzelle 6584 (Steinbruch Carlag) bereits abgebaute Steinblöcke aufzuladen und abzutransportieren. Es handle sich um ca. 150 m3 Stein, die im Steinbruch lagerten. Die Steine würden mittels Pneulader auf Lastwagen geladen und abtransportiert. Es sei mit ca. 40-50 Lastwagenfahrten zu rechnen. Gegen das Gesuch erhoben X._ und weitere Anwohner Einsprache.
Am 24. April 2012 wies die Gemeinde Vals das Baugesuch ab und hiess die dagegen erhobenen Einsprachen gut. Sie verwies auf das bundesgerichtliche Urteil 1C_276/2009, wonach der gesamte Abbaubetrieb einzustellen sei, bis eine endgültige Baubewilligung dafür vorliege.
E.
Dagegen erhob die W._ AG am 4. Juni 2012 Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Dieses führte am 5. November 2012 einen Augenschein durch. Am 6. November 2012 hiess es die Beschwerde im Sinne der Erwägungen (teilweise) gut. Es hob die angefochtenen Bau- und Einspracheentscheide vom 24. April 2012 auf und wies die Sache an die Gemeinde zurück, mit der Anweisung, das Baubewilligungsgesuch vom 22. Dezember 2011 mit dem Antrag auf Bewilligungserteilung unter Auflagen an die kantonale Fachstelle zur Prüfung und Erledigung weiterzuleiten.
F.
Am 13. November 2012 leitete die Gemeinde das Gesuchsdossier an das kantonale Amt für Raumentwicklung. Dieses erteilte mit Verfügung vom 6. Dezember 2012 die Bewilligung für Bauten ausserhalb der Bauzone (BAB-Bewilligung); anschliessend bewilligte die Gemeinde Vals das Baugesuch mit der Auflage, dass der Abtransport der Steine nicht zwischen dem 20. Dezember 2012 und dem 7. Januar 2013 erfolgen dürfe, und wies die Einsprache ab. Die (undatierte) Baubewilligung wurde am 12. Dezember 2012 zugestellt.
G.
Am 13. Dezember 2012 erhoben X._ und drei weitere Einsprecher (im Folgenden: die Beschwerdeführer) gegen den verwaltungsgerichtlichen Entscheid vom 6. November 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht. Sie beantragen, der angefochtene Entscheid sei aufzuheben. Im Sinne einer vorsorglichen Massnahme sei die W._ AG (im Folgenden: die Beschwerdegegnerin) anzuweisen, den Auflad und Abtransport der Steine bis zum Entscheid in der vorliegenden Sache zu unterlassen.
H.
Die Beschwerdegegnerin beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Departement für Volkswirtschaft und Soziales Graubünden und das Verwaltungsgericht schliessen auf Abweisung der Beschwerde. Die Gemeinde Vals und das Bundesamt für Raumplanung haben auf eine Vernehmlassung verzichtet.
I.
Mit Verfügung vom 1. Februar 2013 wurde die Beschwerdegegnerin angewiesen, während der Dauer des vorliegenden Verfahrens den Auflad und Abtransport der bereits abgebauten Steinblöcke auf Parzelle 6584 (Steinbruch Carlag) unter Androhung der Straffolgen gemäss <ref-law> zu unterlassen.

Erwägungen:
1.
Angefochten ist ein kantonal letztinstanzlicher Entscheid des Verwaltungsgerichts. Dieser schliesst das Verfahren nicht ab, sondern weist die Gemeinde an, das Bewilligungsgesuch an die kantonale Fachstelle zur Prüfung und Erledigung weiterzuleiten. Es handelt sich somit um einen Zwischenentscheid.
Dagegen ist die selbstständige Beschwerde gemäss <ref-law> nur zulässig, wenn er einen nicht wieder gutzumachenden Nachteil bewirken könnte (lit. a) oder wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (lit. b).
Die Beschwerdeführer berufen sich auf <ref-law>, weil mit der Gutheissung der Beschwerde ein Endentscheid herbeigeführt werden könnte. Dies trifft zu; dagegen liegen die übrigen Voraussetzungen von <ref-law> nicht vor: Es handelt sich um ein Vorhaben von begrenzter Tragweite, das keine weitläufiges Beweisverfahren voraussetzt. Die Beschwerdeführer haben selbst dargelegt, dass das Baugesuchsverfahren bereits durchgeführt und die nachgesuchten Bewilligungen schon erteilt worden sind.
Die Beschwerdeführer machen nicht geltend, dass ihnen ein nicht wieder gut zu machender Nachteil i.S.v. <ref-law> droht. Dies ist auch nicht ersichtlich, können sie doch ihre Rügen mit Beschwerde gegen den Endentscheid vorbringen.
2.
Nach dem Gesagten ist auf die Beschwerde nicht einzutreten. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern auferlegt.
3.
Die Beschwerdeführer haben die Beschwerdegegnerin (W._ AG) für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Gemeinde Vals, dem Departement für Volkswirtschaft und Soziales Graubünden, dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 6. Dezember 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber