This seems to be quite an NP complete problem, meaning that there is no algorithm that solves the problem in polynomial time. What you might be able to do however is just make a simple searching algorithm that searches through the whole space, starting with the next edge so that the total value of the current path is the smallest. the first answer it finds is then your solution. Starting point is arbitrary as you have to find a cycle.

I doubt any closed form complete fast algorithm exists for this problem, so that might be your best bet.

I think you might be completely right though, and just following the euler cycle with the added 5 from getting back to the starting point is the fastest way to go. This seeing as you have to go back one edge from any of the uneven edged vertices anyway, but instead of b f you go b e a b, which is 4 long instead of 5.