First observation is that in a standard MST algorithm like Kruskal's, its correctness only depends on the order of the edges sorted by weight. If the weights are different but the order of the edges is the same, then you still have the same solution (in terms of the list of edges that are part of the MST).

Now imagine a line sweep from left to right (time -ve infinity to +ve infinity). Two straight lines (linear functions) intersect at most once. Since we have M lines, and hence M choose 2 = M * (M-1) / 2 intersection points, that is the maximum possible number of times the order of the edges change.

Moreover, notice that the solution will lie at one of the intersection points (or at the ends of the time intervals). Since the functions above are linear, the cost of the MST as a function of time is a piecewise linear function.

Combining the above two observations, one possible solution is to solve the MST problem O(M^2) times. Since each run of Kruskal's takes O(M log M) time, we could get a total run time of O(M^3 log M).

I think its possible to improve on the above solution runtime. Notice that you are sorting the list of M edges O(M^2) times. But each successive sort only needs us to swap 2 edges. So we in fact need O(1) time for each sort. I don't know if we can take advantage of this property in our disjoint set data structure.

If the edge weights are higher degree polynomials (degree d), then the number of intersection points increases by a factor of d. Moreover, for each time interval between two intersection points, the total cost of the MST will also be a polynomial of degree d. Now, we'll have to additionally figure out the points at which this polynomial obtains the minimum values (we can't assume that the minimum value will be at the ends of the interval). Finding the zeros of a polynomial of degree d is not trivial, but has many known strategies. Read more here: Root-finding algorithm.