The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _________.

Given the MST edges and their weights from the figure:

• $w(A, C) = 9$

• $w(B, C) = 2$

• $w(B, E) = 15$

• $w(E, F) = 4$

• $w(D, F) = 6$

Sum of MST edge weights $= 9 + 2 + 15 + 4 + 6 = 36$.

The non-MST edges are $(A, B)$, $(D, E)$, and $(C, D)$. By the cycle property of Minimum Spanning Trees, the weight of any non-tree edge must be strictly greater than the maximum edge weight on the unique tree path between its endpoints (since all edge weights are distinct integers).

1. For edge $(A, B)$:

   • Path in MST between $A$ and $B$: $A - C - B$.

   • Maximum edge weight on this path $= \max(w(A, C), w(B, C)) = \max(9, 2) = 9$.

   • Therefore, $w(A, B) > 9$.

2. For edge $(D, E)$:

   • Path in MST between $D$ and $E$: $D - F - E$.

   • Maximum edge weight on this path $= \max(w(D, F), w(E, F)) = \max(6, 4) = 6$.

   • Therefore, $w(D, E) > 6$.

3. For edge $(C, D)$:

   • Path in MST between $C$ and $D$: $C - B - E - F - D$.

   • Maximum edge weight on this path $= \max(w(C, B), w(B, E), w(E, F), w(F, D)) = \max(2, 15, 4, 6) = 15$.

   • Therefore, $w(C, D) > 15$.

All 8 edges must have distinct integer weights. The weights already used in the MST are $\{2, 4, 6, 9, 15\}$.

To minimize the total weight:

• For $w(D, E) > 6$, the smallest available integer not in the set is $7$.

• For $w(A, B) > 9$, the smallest available integer not in the set (and distinct from $7$) is $10$.

• For $w(C, D) > 15$, the smallest available integer not in the set (and distinct from $7, 10$) is $16$.

Minimum possible sum of all 8 edge weights: