number of vertices :  12 
number of required edges  10 
1 2 8 8 24
1 3 2 2 2
2 3 5 5 10
4 5 3 3 9
6 7 4 4 7
7 8 9 9 26
8 9 3 3 7
10 11 2 2 2
10 12 4 4 8
11 12 5 5 7
number of non required edges  10 
1 4 9 9 8
1 5 10 10 2
1 6 11 11 4
2 5 13 13 10
2 11 2 2 0
5 6 13 13 3
5 10 14 14 4
6 8 8 8 1
7 10 1 1 0
9 12 3 3 2
