The Trial on the Cliff Shrine Quest is accessible from the North Lomei Labyrinth in the Tabantha region. If you are heading into the labyrinth on ground level from the west, head to the center. If you look on the map you are looking for the wide section protruding in a westerly direction from the center. You can head through the labyrinth to reach this point or climb up the walls and save time.
At the end of the block will be a ladder that leads to stairs that will lead you to the center of the labyrinth and to the shrine. Check out our short guide on the Qaza Tokki Shrine for more information.