Problem statement

Given a graph with $$$n$$$ nodes and $$$m$$$ edges,

• Find a path that starts at a node (the node is not specified).
• Visit each edge at least once.
• End the path at the starting node.
• Minimize the total cost of the tour.

Input

• The number of nodes $$$n$$$ : $$$2 \leq n \leq 20$$$
• The number of edges $$$m$$$ : $$$1 \leq m \leq 100$$$.
• For each edge, provide the source node, destination node, and the cost associated with that edge.

Output

Output the minimum cost of a tour that satisfies the conditions mentioned above.

Note

The path must visit each edge at least once (meaning you can pass the number of time you want), and the tour must end at the starting node.

Can the problem be solved using :

• $$$dp$$$ with bitmask?
• min cost max flow?

If you have any solution feel free to comment on it. Thanks!!!