Helium is rather expensive and hydrogen is a bit of a challenge as well.
How about a hot air balloon shaped more like a glider. The craft would ascend to 5000ft then glide down and forward several miles then repeat as needed to the destination.
Hmmm, this might actually work.