Yes. Suppose graph is connected. Let's do binary search. Suppose we want to check if it's possible to make a spanning tree with $$$mex \geq X$$$. Any spanning tree with $$$mex \geq X$$$ contains subset of edges with weight of first edge equal to 1, weight of second edge equal to 2, etc. Moreover, for every acyclic set of edges with weights $$${1, 2, 3, \ldots, X}$$$ there exists a spanning tree with $$$mex \geq X$$$ (we can simply complete this subset of edges to spanning tree using any edges). So in fact our problem is to check if there exists an acyclic subset of graph's edges with weights equal to $$${1, 2, 3, \ldots, X}$$$. One can see that this subset is a base in intersection of graphic matroid and a colored matroid of graph's edges with weights not exceeding $$$X$$$.