Air Pacific flies direct from Australia (unlikely from Cairns though). Dont have schedule or fares to hand.

Air NZ flies to Nadi via Auckland. Return fares start at $A741+taxes from Brisbane, Sydney or Melbourne. You can purchase one-way fares for approx half this price.