Hint: e.g. for N=6, S=13 edges in mst = N-1 = 5

Consider 3 cases of edge costs:

• 1, 1, 1, 1, 9 (min comes first)
• 2, 2, 3, 3, 3 (average comes first, with rest spread)
• 2, 2, 2, 2, 5 (average comes first, rest at last)