Let $G$ be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of $G$ is 500. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes _______.

A spanning tree of a connected undirected graph with $|V| = 100$ vertices always contains exactly $|V| - 1 = 99$ edges [1].

When the weight of every edge in the graph is increased by a constant $c = 5$, the weight of every spanning tree increases by the exact same amount:

Because the weight of every spanning tree is shifted by the same constant, the tree that was minimum before remains a minimum spanning tree in the modified graph.

Therefore, the new weight of the minimum spanning tree is: