Given a connected undirected weighted graph of n (<= 15) nodes and m(<= 1000) edges.
Every edge is assigned a positive integer which is the length of the edge.
In this graph i need to make the degree of every node even by adding some fake edges between nodes.
The cost of adding a fake edge is the length shortest path between this nodes in the initial graph.
It is obvious that i can use floyd warshall algorithm to compute the shotest path between every pair of nodes. < br> How can I add fake edges with minimum cost ?

Actually this is needed as a sub-problem of another problem i'm trying to solve but can't afford an efficient way.
link: 1086 — Jogging Trails

Your any kind of help will be cordially accepted.
Thanks.