We prove that any graph G=(V,E) with n points and m edges has a spanning tree
T such that sum_{(u,v)∈ E(G)}d_{T}(u,v) = O(m log n log
log n). Moreover such a tree can be found in time O(m log nlog log n). Our
result is obtained using a new petal-decomposition approach which guarantees that
the radius of each cluster in the tree is at most 4 times the radius of the
induced subgraph of the cluster in the original graph.