Stop by a traditional Sarawak longhouse
Gunung Gading National Park (minimum 1 day, travel by land, to see the Rafflesia)
Mulu National Park (minimum 1 night stay, travel by air, to see the largest cave in the world)
You have the option of backpacking, or approaching a tour operator e.g. Borneo Adventure.
