Try warping to the battle tower and then flying from there, via the Fjords, to the mine.