The normal route is pretty straight-forward as you can just walk up to the shaman and fight him to get the key for the prison cell.
