You are given a graph, Each edge has a weight, and the goal is to find the maximum spanning bipartite graph.

First I want to solve this problem like MST with gready, and with 2-SAT. But if we have a graph like this:

6 9

1 2 2

1 3 1

2 3 1

1 4 1

2 4 1

1 5 1

2 5 1

1 6 1

2 6 1

You will fail. You can't choose 1 2 2 be cause you will earn 2 and lost 4.

How can I solve this problem. Please help me and sorry for my bad English.